Red-Black Tree
A self-balancing BST using weaker, cheaper rules than AVL: every node is red or black, and a small set of colour invariants keeps height within 2× the theoretical minimum.
Every node is coloured red or black under four rules: the root is black, red nodes never have a red child, every path from a node to its descendant nil leaves passes through the same number of black nodes (the "black-height"), and nil leaves count as black.
A new node is inserted red. If its parent is black, nothing else is needed. If the parent is red (a violation), the fix depends on the "uncle": a red uncle means a cheap recolour that pushes the fixup up the tree; a black (or missing) uncle means a rotation plus recolour that resolves it locally in O(1).
Compared to AVL, red-black trees allow slightly more imbalance (height up to ~2·log₂(n) vs ~1.44·log₂(n)) in exchange for fewer rotations per insert/delete on average — which is why most language standard libraries (C++ std::map, Java TreeMap) use red-black trees, not AVL.
Operations
| Operation | Complexity |
|---|---|
| search | O(log n) |
| insert (+ fixup) | O(log n), O(1) amortised rotations |
| delete (+ fixup) | O(log n) |
| height | O(log n), ≤ 2·log₂(n+1) |
Where it's used
Language standard-library ordered maps/sets, anywhere insert/delete frequency matters more than the tightest possible height bound.