Performance of height-balanced trees

ABSTRACT

This paper presents the results of simulations that investigate the performance of height-balanced (HB[k]) trees. It is shown that the only statistic of HB[1] trees (AVL trees) that is a function of the size of the tree is the time to search for an item in the tree. For sufficiently large trees, the execution times of all procedures for maintaining HB[1] trees are independent of the size of the tree. In particular, an average of .465 restructures are required per insertion, with an average of 2.78 nodes revisited to restore the HB[1] property; an average of .214 restructures are required per deletion, with an average of 1.91 nodes revisited to restore the HB[1] property. Moreover, the execution times of procedures for maintaining HB[k] trees, for k > 1, are also independent of the size of the tree except for the average number of nodes revisited on a delete operation in order to restore the HB[k] property on traceback. The cost of maintaining HB[k] trees drops sharply as the allowable imbalance (k) increases. Both analytical and experimental results that show the cost of maintaining HB[k] trees as a function of k are discussed.

REFERENCES

• 1: Adel'son-Vel'skii, G.M., and Landis, E.M. An algorithm for the organization of information. Doklady Akad. Nauk. USSR 146, 2 (1962), 263-266.
• 2: Feller, W. An Introduction to Probability Theory and Its Applications. Wiley, New York, pp. 275-279.
• 3: 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]
• 4: Caxton C. Foster, A generalization of AVL trees, Communications of the ACM, v.16 n.8, p.513-517, Aug. 1973 [doi>10.1145/355609.362340]
• 5: 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]
• 6: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 7: Kosaraju, S.R. On information storage and retrieval by AVL trees. In Princeton Conf. on Information Storage and Retrieval, Princeton U., 1973.
• 8: W. A. Martin , D. N. Ness, Optimizing binary trees grown with a sorting algorithm, Communications of the ACM, v.15 n.2, p.88-93, Feb. 1972 [doi>10.1145/361254.361259]
• 9: Nievergelt, J., and Reingold, E.M. Binary search trees of bounded balance. SIAM J. Computing 4, 1 (March 1973), 33-43.
• 10: K. C. Tan, On Foster's information storage and retrieval using AVL trees, Communications of the ACM, v.15 n.9, p.843, Sept. 1972 [doi>10.1145/361573.361588]
• 11: Stone, H., and Siewiorek, D.P. Introduction to Computer Organization and Data Structure, PDP-11 Ed. McGraw-Hill, New York, 1975.
• 12: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]

INDEX TERMS

Keywords:
AVL trees, HB[k] trees, balanced trees, information storage and retrieval, searching