Red-Black Trees — Data Structures Course

What you'll learn

The red-black tree is the self-balancing BST inside most standard libraries (Java's TreeMap, C++'s std::map, Linux's scheduler). It balances more loosely than AVL — using node colors — which makes inserts and deletes faster.

By the end you'll be able to:

State the red-black invariants
Repair a violation by rotation or by recoloring
Choose between AVL and red-black trees

The red-black rules

Every node is colored red or black, and these invariants always hold:

The root is black.
A red node's children are both black (no two reds in a row).
Every path from a node to its leaves passes through the same number of black nodes.

Together these force the longest path to be at most twice the shortest — good enough to guarantee O(log n) height, without AVL's stricter (and costlier) balancing.

Fix by rotation

When a new red node's parent is red and its uncle is black, we rotate and swap colors — just like AVL, plus a recolor:

Red-red violation, black uncle → rotate + recolor

Insert with rotation

1/4Insert 10. The root is always black.

Red and black fills show the colors; the ring highlights the nodes in play.

Fix by recoloring

When the uncle is red, no rotation is needed at all — just recolor and push the problem up toward the root. This cheap fix is what makes red-black inserts fast:

Red-red violation, red uncle → recolor only

Insert with recolor

1/3Start: 20 (black) with red children 10 and 30.

AVL vs red-black

	AVL tree	Red-black tree
`Balance`	Strict (bf in {−1,0,1})	Loose (paths ≤ 2× apart)
`Height`	≤ 1.44 log n	≤ 2 log n
`Lookups`	Slightly faster (shorter)	Slightly slower
`Insert / delete`	More rotations	Fewer rotations — faster
`Best for`	Lookup-heavy workloads	General maps/sets (the common default)

In code

Language

redblack.py

# After a normal BST insert of a RED node z, repair upward:
def fix_insert(z):
    while z.parent and z.parent.color == RED:
        if uncle(z) is RED:               # Case 1
            z.parent.color = BLACK
            uncle(z).color = BLACK
            grandparent(z).color = RED
            z = grandparent(z)            # keep checking upward
        else:                             # Case 2 / 3
            z = rotate_and_recolor(z)     # rotate, swap parent/grandparent colors
    root.color = BLACK                    # the root is always black

Note

Red-black deletion has more cases than insertion, but the same idea: fix violations locally with rotations and recoloring, walking up toward the root — all in O(log n).

Recap & quick check

Key takeaways

Red-black trees balance using node colors and three invariants.
Root is black; no two reds in a row; equal black-height on all paths.
A red-red violation with a black uncle is fixed by rotation + recolor.
A red-red violation with a red uncle is fixed by recoloring only (cheap).
They balance more loosely than AVL, so updates are faster — the common library default.

Quick check

1. What color is the root of a red-black tree?

2. Which red-black invariant prevents long thin paths?

3. If a new red node's parent and uncle are both red, you:

4. Compared to AVL trees, red-black trees:

That's balanced search trees. Next, a different tree shape optimized for always finding the min or max instantly. Next up: Module 20 — Heaps & Priority Queues.