"Rank- balanced trees" by Haeupler(RB) trees are a class of balanced trees that includes AVL trees, Sen and Tarjan defines a framework for kinds of balanced tree methods that encompasses red-black and AVL trees, among others. They introduce a new method in this framework called "weak AVL", or "wavl" trees that combine the best aspects of red-black and AVL treend others. Weak AVL (wavl) trees are a recently discovered member of that class. This change replaces red-black rebalancing with weak AVL rebalancing in the RB tree macros.
This patch takes "RB_" to denote "rank-balanced" and changes the balancing method from "red-black" to "wavl" for the RB macrosRemoving a node from a wavl tree never requires more than two rotations, which is better than either red-black or AVL trees. Inserting a node into a wavl tree never requires more than two rotations, which matches red-black and AVL trees.
Wavl trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have all the advantages of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can start to get red-blackier.
The only disadvantage of wavl trees to red-black trees is that, while no insertion adjusts the tree too much, more insertions are likely to adjust the tree a bit. That's the cost of keeping the tree more balanced.
Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing.