Chapter 6: Balanced Trees and Red-Black Trees

Vol 2: Algorithm Forest Adventure · Station 6

---

Metadata Card

Attribute	Value
Prerequisites	BST (Chapter 5)
Difficulty	(Advanced)
Keywords	AVL Tree Red-Black Tree Rotation Balance Factor TreeMap B-Tree

---

Your Progress

You've entered the "Unbalanced Swamp." Trees here lean left or right — some have collapsed into straight sticks. These are BSTs that degenerated from inserting ordered data.

---

Breakthrough · Origins

AVL Tree: Balance Factor

Any node's left and right subtree heights differ by at most 1.

Balance Factor = height(left) - height(right)
Allowed range: {-1, 0, 1}

AVL Four Rotations

def _rotate_right(self, y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
    x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
    return x

def _rotate_left(self, x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
    return y

Four cases: LL (right rotate), RR (left rotate), LR (left then right), RL (right then left).

Red-Black Tree: Five Properties

1. Every node is red or black
2. Root is black
3. Leaves (NIL) are black
4. Red node's children are black (no consecutive reds)
5. All paths from any node to leaves have the same number of black nodes

Guarantee: Longest path ≤ 2 × shortest path.

AVL vs Red-Black

Feature	AVL	Red-Black
Lookup	Faster (strict O(log n))	Slightly slower (≤ 2log n)
Insert/Delete	More rotations	Fewer rotations (≤ 3)
Implementation	Simpler	More complex
Space	Height field (int)	Color field (1 bit)

Why TreeMap uses Red-Black: General-purpose containers need balanced write/read performance. Red-Black's fewer rotations win for insertion-heavy workloads.

---

Verification Checklist

• [ ] Can draw AVL four rotations
• [ ] Can recite Red-Black's five properties
• [ ] Can explain why TreeMap uses Red-Black over AVL
• [ ] Can describe B+ tree's advantage for range queries

---

Traveler's Notes

• AVL: strict balance, more rotations
• Red-Black: loose balance, fewer rotations, industry standard
• B-Tree/B+ Tree: minimize disk I/O by storing more keys per node

---

→ Next Stop Preview

Chapter 7: Heaps and Priority Queues — "Always knowing the most urgent task."