Skip to main content
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1nz5z
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHaeupler, Bernhard-
dc.contributor.authorSen, Siddhartha-
dc.contributor.authorTarjan, Robert E-
dc.date.accessioned2021-10-08T19:47:35Z-
dc.date.available2021-10-08T19:47:35Z-
dc.date.issued2015-06en_US
dc.identifier.citationHaeupler, Bernhard, Siddhartha Sen, and Robert E. Tarjan. "Rank-Balanced Trees." ACM Transactions on Algorithms 11, no. 4 (2015): 30:1-30:26. doi:10.1145/2689412en_US
dc.identifier.issn1549-6325-
dc.identifier.urihttps://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/WADSrb-trees.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1nz5z-
dc.description.abstractSince the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of ranks and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree), whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.en_US
dc.format.extent30:1 - 30:26en_US
dc.language.isoen_USen_US
dc.relation.ispartofACM Transactions on Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleRank-Balanced Treesen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1145/2689412-
dc.identifier.eissn1549-6333-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
RankBalancedTrees.pdf182.3 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.