Red-black trees

Balance a BST with node colors + four rules. The balanced tree inside most standard-library maps.

Four rules = a balance budget

1. Every node red or black
2. Root is black
3. No two reds in a row
4. Equal black-height on every root-to-leaf path

→ longest path ≤ 2× shortest → height ≤ 2·log₂(n+1)

Watch the colors balance it

New nodes arrive red; recolor/restructure to keep the rules. Insert 1..7 sorted → balanced, never a chain.

Balanced, a touch taller than AVL

At 100000: RB height 22 (bound 33), AVL was 17, plain BST 100000. 68× faster at n=8000.

Why libraries pick red-black

• Looser balance → fewer rotations per update than AVL
• Slightly taller, but cheaper to maintain under reads AND writes
• A red-black tree is a 2-3-4 tree (a B-tree of order 4) in disguise

Takeaway

The pragmatic balanced tree: guaranteed O(log n), cheap updates, everywhere. Next: the binary heap — give up search order to grab the max fastest.