Optimizing binary trees grown with a sorting algorithm

ABSTRACT

Items can be retrieved from binary trees grown with a form of the Algorithm Quicksort in an average time proportional to log n, where n is the number of items in the tree. The binary trees grown by this algorithm sometimes have some branches longer than others; therefore, it is possible to reduce the average retrieval time by restructuring the tree to make the branches as uniform in length as possible. An algorithm to do this is presented. The use of this algorithm is discussed, and it is compared with another which restructures the tree after each new item is added.

REFERENCES

• 1: Adel'son-Vel'skiy, G.M., and Landis, Ye.M. An algorithm for the organization of information. Doklady Akad. Nauk USSR Moscow 16, No. 2 (1962), 263-266. Also available in translation as U.S. Dept. of Commerce OTS, JPRS 17,137, Washington, D.C., and as NASA Document N63-11777.
• 2: C. C. Foster, Information retrieval: information storage and retrieval using AVL trees, Proceedings of the 1965 20th national conference, p.192-205, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806043]
• 3: Hibbard, T.N. Some combinatorial properties of certain trees with applications to searching and sorting. J. ACM 6 (May 1963), 206-213.
• 4: C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Knuth, D.E. Stanford Comput. Sci. Dept. Memo. Stanford U, Calif.
• 7: Gary D. Knott, A balanced tree storage and retrieval algorithm, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511305]

INDEX TERMS

Keywords:
global and local optimization, recursion, retrieving information from binary trees, sorting