A proposal to redefine RB trees

I have a change ready to commit at https://reviews.freebsd.org/D25480
that would redefine the tree-balancing criteria for the RB tree macros,
changing them from red-black trees to the weak-AVL trees described in
the paper "Rank-balanced trees" by Haeupler, Sen and Tarjan.  By happy
coincidence (or the authors' deliberate scheme), the letters RB can
represent "Rank-balanced" as easily as "red-black", so no global
renaming is required.

This change does not add or remove fields.  It does keep a tighter
balance constraint than red-black trees, so that in conditions where
balancing really matters (for example, when inserting tree nodes in
sorted order), weak-avl trees produce a better balanced tree and faster
lookups.  That same tighter balance constraint means that an insert
operation is more likely to lead to restructuring of the tree than
before, for which there is a small performance cost.

The original paper at
http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf provides more
analysis of the relative benefits of weak-avl trees.

Are there any objections?

Doug Moore (dougm_at_freebsd.org)