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

[Joerg Sonnenberger]

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
http://cvsweb.netbsd.org/bsdweb.cgi/src/common/lib/libc/gen/rb.c?rev=1.11&content-type=text/x-cvsweb-markup&only_with_tag=MAIN
http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/rbtree.h?rev=1.2&content-type=text/x-cvsweb-markup

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

Joerg