libredblack 1.3

libredblack is 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:

Every node is either Red or Black.

A leaf node (a dummy empty node at the end of the tree) is always Black.
If a node is Red then its children are Black.

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, thats 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).