rb.h -- Red-black tree implementation

rb.h implements left-leaning 2-3 red-black trees as C preprocessor macros, and is used extensively in jemalloc. Similar implementations predate this one, such as OpenBSD's sys/tree.h and my own obsolete rb.h and rb.h. However, most of those implementations require approximately four pointer-size fields per node (left child, right child, parent, color), whereas this one requires only two (left child, right child + color). The only notable disadvantage is that insertion/removal are ~1.5X slower than the fastest implementations, due to extra overhead for maintaining the current path through the tree. For more discussion, see this blog post.

For those concerned about correctness and performance, a test program and benchmark program are available. Comparable benchmark programs are also available for sys/tree.h and for my old implementations (1, 2).

Copyright © 2010 Jason Evans <jasone@canonware.com>.
Last updated 2010/04/18.


Modern rb.h
Obsolete rb.h (1)
Obsolete rb.h (2)