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