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