RedBlack Balanced Tree Searching and Sorting Library - Damian Ivereigh

What is it and how does it work?

What is it?: A library to provide the RedBlack balanced tree searching and sorting algorithm. The algorithm was taken from the book "Introduction to Algorithms" by Cormen, Leiserson & Rivest. Frankly I never entirely understood it, but it most definately works!

What is the problem with normal binary trees?: A standard binary tree only works well if the original data is provided in a random order (random in terms of the key being sorted on). If however the data is provided in order, then the tree becomes very un-balanced and searches degrade into nothing more than a linked list.

How is the RedBlack tree different?: The RedBlack tree acts in a way to keep the overall tree fairly balanced as new data is loaded in.

How does it work?: The tree is always organised such that it has the following properties:

1. Every node is either Red or Black.
2. A leaf node (a dummy empty node at the end of the tree) is always Black.
3. If a node is Red then it's children are Black.
4. Every path from the root to a leaf contains the same number of Black nodes.

So from 3 & 4 above, we can see that the longest path (alternating Red and Black nodes) is only twice as long as the shortest path (all Black nodes). Thus the tree remains fairly balanced.

Great! How does it maintain those properties?: Ah, well, that's where I get a bit hazy. I know that it does this by adding Red nodes and then rotating the tree elements and changing the colours to sort out times when two Red nodes become parent-child (breaking rule 3).

How stable is the code?: Very. I have used this at the heart of the SDDB directory service for several years now, which itself is the heart of the Cisco Enterprise Print System(CEPS). It performs at least a couple of hundred lookups a second day in and day out. It has also been used as the main indexing system in DENTS.

What license is it released under?: The code is released under the LGPL (the GNU Library Public License). However contact me damian@cisco.com if you would like a different license.

• Latest news (25-Oct-2003): Version 1.3 is out! After almost 2 years of inaction, we finally have something new: Eric Raymond's code generator: rbgen.

  This creates redblack code to be included into your program which gets around a bunch of the type mangling required when using the library. Eric's idea is to allow the use of associative arrays (like perl or python hashes) within C. See the man page: rbgen.1 for more information.

Download

Source and Binary RPMS

Documentation

The man pages: rbinit.3, rbopenlist.3 and rbgen.1

The Sourceforge project page: libredblack

Comments? Contact me at damian@cisco.com

Last updated 25-Oct-2003