# Red-Black Trees

Every node in a red-black tree is colored either red or black.
They guarantee *O(lg n)* time per access by
adjusting tree structure so that the following properties
are always maintained.
- The root is always black.
- Every path on the tree, from the root down to the exterior,
has the same number of black nodes.
- No red node has a red child.

They provide an efficient binary tree-based implementation of
2,3,4-trees. (*I.e.* like *B*-trees, for *B*=4.
This representation is available from the last menu below.)
Every node on the resulting tree is guaranteed to have a depth less than
*2 lg n* in the worst case. Moreover, the required overhead
is very small: there are never more than 2 rotations required for
an insertion, and never more than *m* "recoloring events" in
any sequence of *m* insertions - *i.e.* a constant amount
of extra work per operation (amortized) for all the required
bookkeeping and restructuring.
This demo begins with a "worst case" sequence of 14 insertions,
and then turns over control to the user.
Note that deletion is not yet implemented!

The Source.