TY - GEN
T1 - Rank-balanced trees
AU - Haeupler, Bernhard
AU - Sen, Siddhartha
AU - Tarjan, Robert E.
PY - 2009
Y1 - 2009
N2 - Since the invention of AVL trees in 1962, a wide variety of ways to balance 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 introduce the rank-balanced tree, a relaxation of AVL trees. Rank-balanced trees can be rebalanced bottom-up after an insertion or deletion in O(1) amortized time and at most two rotations worst-case, in contrast to red-black trees, which need up to three rotations per deletion. Rebalancing can also be done top-down with fixed lookahead in O(1) amortized time. Using a novel analysis that relies on an exponential potential function, we show that both bottom-up and top-down rebalancing modify nodes exponentially infrequently in their heights.
AB - Since the invention of AVL trees in 1962, a wide variety of ways to balance 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 introduce the rank-balanced tree, a relaxation of AVL trees. Rank-balanced trees can be rebalanced bottom-up after an insertion or deletion in O(1) amortized time and at most two rotations worst-case, in contrast to red-black trees, which need up to three rotations per deletion. Rebalancing can also be done top-down with fixed lookahead in O(1) amortized time. Using a novel analysis that relies on an exponential potential function, we show that both bottom-up and top-down rebalancing modify nodes exponentially infrequently in their heights.
UR - http://www.scopus.com/inward/record.url?scp=70049086658&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70049086658&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03367-4_31
DO - 10.1007/978-3-642-03367-4_31
M3 - Conference contribution
AN - SCOPUS:70049086658
SN - 3642033660
SN - 9783642033667
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 351
EP - 362
BT - Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
T2 - 11th International Symposium on Algorithms and Data Structures, WADS 2009
Y2 - 21 August 2009 through 23 August 2009
ER -