Red-Black Trees

A binary tree is an efficient way to store and retrieve ordered data if the tree is balanced. Various strategies exist for keeping a tree balanced even under insertions and deletions of new tree elements. These all consist of shifting data around the tree to keep the contents of the two child for each node approximately equal. The shifting has to be done in an incremental and local manner, making small changes along the search or insertion path, so that the method does not consume more time than the improvement is ultimately worth.

Here is an implementation of a red-black tree, demonstrating the following discussion:

The Red-Black tree colors the nodes Red or Black, and uses the length of black paths to signal a local change in the tree structure. Although the nodes are Red or Black, the depiction usually shows the edges as being red or black, the correspondence being that the edge has the color if the child node which it leads to. The rules for a Red-Black tree are simple:

  1. Each path from root to leaf has the same number of black edges.
  2. Red edges do not occur immediately next to each other on a path from root to leaf.
This implies that the longest path from root to leaf in the tree is at most twice as long as the shortest path from root to leaf.

In general, we can add nodes to the tree by making them red. This does not disturb the balance in so far as looking only a path lengths of black edges. Sometimes we cannot add red edges, because the parent edge is also red. We then do a local transformation to place the pair of red edges in a sibling relationship, rather than a parent-child relationship. Additional care is required to make sure that ths transformation does not create elsewhere the same problem it is intended to solve: the pairing up immediately adjacent of red edges on a path from root to some leaf.

To be precise, the really bad situation is when the red edge is not only a child of a red edge, but that that it's Uncle is also red. That is, the red parent edge has a red sibling edge. A second technique is employed to avoid this bad possibility. When searching down the tree, if a sibling pair are both red, the red edges are combined and passed up to the parent. This has the effect of smoothing out the placement of red edges. It amounts to doing a little work slowly, combining up red edges and straightening out the result little by little, instead of having to do a lot of work all at once.