Red-Black Tree — Balanced BST with Color Invariants

Why it matters

Red-black trees underlie most library ordered maps. Understanding enables informed use.

The architecture

Colors: red or black.

Invariants: root black; red has black children; equal black-heights all root-to-leaf paths.

How it works end to end

Insert: color new node red; fix violations via rotations + recoloring.

Delete: complex case analysis; rebalance from parent.

Use: Java TreeMap, C++ std::map, Linux CFS scheduler.