Balancing binary trees by internal path reduction
- 1 December 1983
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 26 (12) , 1074-1081
- https://doi.org/10.1145/358476.358509
Abstract
We present an algorithm for balancing binary search trees. In this algorithm single or double rotations are performed when they decrease the internal path of the total tree. It is shown that the worst internal path on such trees is never more than 5 percent worse than optimal and that its height is never more than 44 percent taller than optimal. This compares favorably with the AVL trees whose internal path may be 28 percent worse than optimal and the same 44 percent worst height, and with the weight-balanced trees which may be 15 and 100 percent worse than optimal, respectively. On the other hand, the number of rotations during a single insertion/deletion can be O(n), although the amortized worst-case number of rotations is O(log n) per update.Keywords
This publication has 21 references indexed in Scilit:
- Addendum to “a storage scheme for height-balanced trees”Information Processing Letters, 1979
- A Partial Analysis of Random Height-Balanced TreesSIAM Journal on Computing, 1979
- A storage scheme for height-balanced treesInformation Processing Letters, 1978
- Insertions and deletions in one-sided height-balanced treesCommunications of the ACM, 1978
- A comparison of tree-balancing algorithmsCommunications of the ACM, 1977
- An insertion technique for one-sided height-balanced treesCommunications of the ACM, 1976
- Performance of height-balanced treesCommunications of the ACM, 1976
- Weight-balanced treesPublished by Association for Computing Machinery (ACM) ,1975
- A generalization of AVL treesCommunications of the ACM, 1973
- Information retrievalPublished by Association for Computing Machinery (ACM) ,1965