Red-Black Trees

The Red-Black tree keeps a BST balanced by coloring every node red or black and enforcing invariants that limit imbalance to a factor of two. It backs std::map/std::set in C++, TreeMap/TreeSet in Java, and the Linux CFS scheduler.

The Four Invariants

1. Every node is red or black (including leaves).
2. The root is black.
3. Red nodes have only black children — no two reds may be adjacent.
4. Every path from root to a leaf contains the same number of black nodes — the tree’s black-height.

Together, invariants 3 and 4 cap the height at 2 · log₂(n+1) — the longest path (alternating red/black) can be at most twice the shortest (all-black).

Insert: Red First, Fix Later

Insert the new node as a red leaf — this preserves black-height (invariant 4) and only risks violating invariant 3. The fix-up walks up while the parent is red, handling each case:

while parent is RED:
  if uncle is RED:
      recolor parent + uncle BLACK, grandparent RED
      move up to grandparent
  else:  # uncle is BLACK → rotations
      if z is inner child: rotate parent, descend
      rotate grandparent, swap colors
color root BLACK

• Recoloring costs O(1) per level and pushes the violation upward.
• Rotations terminate the loop: after a rotation the violation is resolved for good.

Why Library Maps Prefer Red-Black

Insert in a Red-Black tree does at most two rotations and then only recolors up the path — for frequent insertions this beats the AVL tree’s stricter rebalancing. That is why Red-Black is the default for most library containers.

Practice Trajectory

1. Draw the insert fix-up cases for a sequence that triggers each one.
2. Implement colored nodes and BST-insert, then add the recolor cases (1a/1b).
3. Add the rotation cases (2a/2b) and verify all four invariants after every insert.
4. Implement the delete fix-up (it has six cases — the hardest classic tree fix-up).
5. Compare tree heights and rotation counts against an AVL tree on random and sorted inputs.