Red–black tree

Results

• smallest is alway left-most

Properties

• Every node is either red or black

• The root and leaves are black

• If a node is red, then its parent is black

• All simple paths from any node $x$ to a descendant leaf have the same number of black nodes
• $black-height(x)$
• Simple paths means path without repetition

Theorem

• Merge red nodes into their black parents

• This process produces a tree in which each node has 2,3, or 4 children

• The 2-3-4 trees has uniform depth $h'$ of leaves

Corollary

• search, min, max, successor, predecessor all run in $lg(n)$

insertion and deletion through rotation run in $lg(n)$

1. insert

2. recolor

3. right rotate child

4. left rotate parent

5. recolor

Enhancement