A red-black tree is a binary search tree that stays balanced using one cheap trick: every node is painted red or black, and a handful of color rules force the tree to stay roughly even. It accepts a slightly looser balance than an AVL tree in exchange for doing fewer rotations on insert and delete — which is why it backs many standard-library maps and OS schedulers.
The color rules
1Every node is red or black; the root is black.
2No red node may have a red child (the red-red rule).
3Every path from a node down to an empty leaf crosses the same number of black nodes — its black-height.
Why these rules force balance
Equal black-height on every path means no path can have more black nodes than another. And since reds can't stack, the longest possible path (alternating red-black) is at most twice the shortest (all black). A factor-of-two height bound is all you need to guarantee O(log n).
Fixing an insert — recolor before you rotate
A new node always arrives red (adding a red node never changes any path's black-height, so it's the least disruptive choice). If its parent is black, you're done. If the parent is also red, the red-red rule breaks and you fix up — and the uncle (the parent's sibling) decides how:
1Uncle is red -> just recolor: flip the parent and uncle to black and the grandparent to red, then repeat the check upward from the grandparent. No rotation needed.
2Uncle is black -> rotate: a single or double rotation around the grandparent, plus a recolor, repairs the structure locally and terminates.
red-red violation, RED uncle -> recolor only:
G(black) G(red)
/ \ / \
P(red) U(red) --> P(black) U(black)
/ /
N(red) <- new N(red) (now legal; re-check at G)
AVL vs red-black, again
AVL keeps height tighter, winning on lookups. Red-black tolerates more imbalance but guarantees at most a constant number of rotations per update — winning on insert/delete-heavy workloads. Both are O(log n); the constant factors differ.
Recolors can cascade, rotations can't
The red-uncle case can ripple recoloring all the way up to the root — that's still O(log n) work but many cheap steps. A single insert never needs more than two rotations to settle, no matter the tree size.
