RedBlack Balanced Tree Searching and Sorting Library
|
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:
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
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.
The man pages: rbinit.3, rbopenlist.3 and rbgen.1
The Sourceforge project page: libredblack
Comments? Contact me at Last updated 25-Oct-2003
Download
Documentation