Academic
Publications
Rank-Balanced Trees

Rank-Balanced Trees,10.1007/978-3-642-03367-4_31,Bernhard Haeupler,Siddhartha Sen,Robert Endre Tarjan

Rank-Balanced Trees   (Citations: 4)
BibTex | RIS | RefWorks Download
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.
Conference: Workshop on Algorithms and Data Structures - WADS , pp. 351-362, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably red-black trees [9] and the recently introduced rank-balanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
    • ...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably red-black trees [9] and the recently introduced rank-balanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
    • ...To obtain our bounds we use an exponential potential function, an idea we have also used [10] to analyze rank-balanced trees...
    • ...needed in AVL [2], rank-balanced [10], and red-black trees [9]...
    • ...Our tree terminology is the same as in [10]...
    • ...An exponential potential function of the kind rst used by us to analyze another kind of balanced tree [10] gives our most important result: a ravl tree built from an empty tree has height logarithmic in the number of insertions, even if deletions are intermixed arbitrarily...
    • ...These results hold for rank-balanced trees and red-black trees, but the constant factors are worse [10]; they do not hold for AVL trees subject to intermixed insertions and deletions...
    • ...In our preliminary experiments, we compared ravl trees (without periodic rebuilding) to standard red-black trees [9] and rank-balanced trees [10] on typical input sequences...

    Siddhartha Senet al. Deletion Without Rebalancing in Balanced Binary Trees

    • ...Some of them guarantee an O(1) worst-case number of structural changes (pointers/fields modifications) after an insertion or a deletion operation [12,19,11,13,10,6]...

    Prosenjit Boseet al. Skip Lift: A Probabilistic Alternative to Red-Black Trees

    • ...We use exponential potential functions similar to those we have used to analyze balanced binary trees [9, 19]...
    • ...We have obtained similar results for balanced binary trees [9, 19]...

    Siddhartha Senet al. Deletion without Rebalancing in Multiway Search Trees

    • ...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably red-black trees [9] and the recently introduced rank-balanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
    • ...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably red-black trees [9] and the recently introduced rank-balanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
    • ...To obtain our bounds we use an exponential potential function, an idea we have also used [10] to analyze rank-balanced trees...
    • ...needed in AVL [2], rank-balanced [10], and red-black trees [9]...
    • ...Our tree terminology is the same as in [10]...
    • ...An exponential potential function of the kind rst used by us to analyze another kind of balanced tree [10] gives our most important result: a ravl tree built from an empty tree has height logarithmic in the number of insertions, even if deletions are intermixed arbitrarily...
    • ...These results hold for rank-balanced trees and red-black trees, but the constant factors are worse [10]; they do not hold for AVL trees subject to intermixed insertions and deletions...
    • ...In our preliminary experiments, we compared ravl trees (without periodic rebuilding) to standard red-black trees [9] and rank-balanced trees [10] on typical input sequences...

    Siddhartha Senet al. Deletion Without Rebalancing in Balanced Binary Trees

Sort by: