Red-Black trees in brief

Before talking more on Agents – autonomous objects, I thought I would write on Red-black trees. Not that it relates to Agents in any direct fashion rather they are interesting.

Why Red-Black trees?

We all, probably, went through lot of hell trying to understand binary search trees (BST) and programming all those operations – searching, inserting, deleting, and finding maximum and minimum – while trying to understand pointers. We were made to believe that BST’s are worth all that trouble because they run asymptotically faster than some of the other data structures like linear lists. The mentioned operations run in Θ(lgn) time in worst case for a complete binary search tree. However, if the tree is nothing but linear list of n-nodes, we get a worst case running time of Θ(n). So for a BST, the expected time is Θ(lgn) but its not a guarantee. We need a guarantee, and that’s what Red-black trees give us (of course Θ(lgn) is asymptotically greater than Θ(n), else why the trouble?)

Features:

1. It is a balanced tree, so that it guarantees the running time of Θ(lgn). Some of the other trees do the same: AVL-trees, 2-3 trees, 2-3-4 trees.
2. RB-trees have an additional one bit that represents the color of the node – red or black.
3. It defines a way to color the nodes so that it can approximately balance the tree.
4. A path from a node to leaf is at most twice longer than any other path.

Any operations on RB trees maintain the following 4 properties.

1. Every node is either red or black.
2. Every leaf (those are nil’s) and the root is black.
3. Every red node has black children or every red node has a black parent.
4. For every node x, all the paths from it to the descendant leaves contain same number of black nodes. This is the black-height of the node x, bh(x), that excludes the node itself. The above properties ensure that the RB-tree is always balanced

The red-black tree has height of at-most 2lg(n+1), where n is the number of internal nodes. (Can be proved by induction). This guarantees that the dynamic operations of search, insert, delete, finding minimum and maximum, locating predecessor and successor can take place in O(lgn). With little more sweat while programming, we have a guarantee. Sweet.

Links for more on Red-black trees: MIT slides, MIT talk, Wikipedia.