[cfe-dev] libc++ red-black tree: halving the branches

Joerg Sonnenberger joerg at britannica.bec.de
Thu Apr 5 07:24:01 PDT 2012

On Wed, Apr 04, 2012 at 08:58:35PM -0400, Sean Silva wrote:
> I came up with a neat little trick (that may have already been considered)
> that halves the number of conditionals in the venerable red-black tree
> rebalancing operations. The key observation is that there is a big `if`
> whose two branches are identical except that "left" and "right" are
> switched.

You might want to look at

for a version of red-black trees aggressively exploiting the symmetry.


More information about the cfe-dev mailing list