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.