## 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:

- Each path from root to leaf has the same number of black
edges.
- 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.