Red-Black Trees

These properties include:


1)There are never two red links in a row along any path from the
root to an external node.

2)The search procedure for a standard binary tree works without
modification.

3)No overhead is added by the balancing mechanism to the time taken
by the fundamental searching procedure. Since each key is inserted 
just once, but may be searched for many times in a typical application,
the end result is that we get improved search times (because the trees
are balanced) at relatively low cost (because no work for balancing
is done during the searches).

4)The overhead for insertion is very small: we have to do something
different only when we see 4-nodes, and there aren't a lot of 4-nodes
in the tree because we are always breaking them up. The inner loop
only needs one extra test (if a node has two red children, it's part
of a 4-node), as show in the following implementation of the 
insertion procedure: