Rank-Balanced Trees

Since 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, abbreviated 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.