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.

Delete: The Six-Case Fix-Up

Deletion is harder because removing a node can disturb black-height (invariant 4) — the rarer and costlier violation. First do a standard BST delete; then, if the removed node was black, the tree is short one black node on that path. Let x be the node that “doubly black” replacement (a null leaf counts as black), and fix up:

1. x is red → color it black and you’re done (a red node replacing the removed black restores the count).
2. Otherwise x is doubly-black. Walk up while x is not root and x is black, handling cases by sibling w:
   • Case 1 — w is red: recolor w black, parent red, rotate left over parent; the new sibling is black, so the case reduces to 2–4.
   • Case 2 — w is black, both of w’s children black: push x’s blackness up — make w red, set x = parent, continue (parent may now be the doubly-black node).
   • Case 3 — w is black, w’s left child red, right child black: recolor w’s left child black, w red, rotate right over w; now the sibling has a red right child → Case 4.
   • Case 4 — w is black, w’s right child red: rotate left over parent, swap colors of parent and w, set w’s right child black, and done — black-height is restored.
3. After the loop, color the current node black (fixes the root or the final case).

The mnemonic: red sibling → rotate to get a black sibling; both-black children → push blackness up; then rotate the corner into a line and resolve with the final rotation. The whole sequence does at most three rotations and the rest is recoloring — same amortized O(log n) as insert.

The 2-3-4 Tree Correspondence

A Red-Black tree is a binary encoding of a 2-3-4 tree (a B-Tree of order 4). Every black node, together with its red children, forms one 2-3-4 node:

• A single black node with no red children ↔ a 2-node.
• A black node with one red child ↔ a 3-node (the red child can sit on the left or right — the two orientations are the two 3-node shapes).
• A black node with two red children ↔ a 4-node.

2-node:   (5)       3-node:   (5)      4-node:   (5)
                            /            /  |  \
          black only    (3)          (3)(7)      ← red children
                          red

Reading down: each red child “belongs” to its black parent, so the invariant “no adjacent reds” is exactly “a 3-4 node never has more than three children,” and the equal-black-height rule is “every 2-3-4 path from root to leaf passes through the same number of black nodes” — i.e. same number of 2-3-4 levels.

This correspondence is why the fix-ups feel mechanical: a Red-Black split is a 2-3-4 node growing a fourth child (uncle is red → recolor), and a rotation is a 2-3-4 node “rearranging” when it can’t absorb another child. Proofs of the Red-Black height bound are cleanest through the 2-3-4 lens: a 2-3-4 tree with n nodes has height O(log n), and the red-black encoding at most doubles it.

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. Map a Red-Black tree to its equivalent 2-3-4 tree and verify the correspondence.
6. Compare tree heights and rotation counts against an AVL tree on random and sorted inputs.