Red-Black Tree
Last Updated: May 30, 2026
AVL trees solve the BST-degenerates-to-a-list problem with a strict height invariant. They work, but the strictness has a cost: deletion can trigger up to O(log n) rotations, and every node stores a 4-byte height.
Red-black trees take a different approach. They relax the balance requirement just enough that any insertion or deletion can be repaired with at most 2 or 3 rotations and some color flips, regardless of tree size. The height is no longer the tightest possible, but every operation has bounded rebalancing work. That predictability is why almost every production sorted map, Java's TreeMap, C++'s std::map, the Linux kernel's process scheduler and epoll, ships a red-black tree internally.
In this chapter, we'll cover:
- The five properties that define a red-black tree
- Why those properties bound the height at
2 · log2(n + 1) - Insertion: insert red, then fix three cases
- Deletion: replace as in a BST, then resolve double-black with four cases
- Visual walkthroughs of every case
- A complete, working implementation
- How red-black trees compare to AVL in real systems
The rotations used here are the same left and right rotations introduced in the AVL Tree chapter, applied with a different rebalancing rule.