Coloring nodes
A red black tree is a binary search tree where every node carries one extra bit: a color, red or black. By constraining how colors may appear, the tree stays approximately balanced without the strict height rule that AVL trees enforce.
The five rules
- Every node is either red or black.
- The root is black.
- Every leaf, here meaning the null sentinels, is black.
- A red node never has a red child, so reds cannot chain.
- Every path from a node down to its descendant leaves contains the same number of black nodes. This count is the black height.
Why balance follows
Because no two reds touch, the longest root to leaf path is at most twice the shortest. That bound keeps the height within a constant factor of the logarithm of the node count, so operations stay fast.
Fixing violations
Insertion colors the new node red, which can only break the no double red rule. We repair it by recoloring an uncle or by rotating a parent and grandparent. Deletion can break the black height rule and is repaired with a similar mix of recolors and rotations.
Key idea
The no double red rule plus equal black heights keep the longest path under twice the shortest, giving balance without exact height bookkeeping.