← Back to the red black trees page
Red-Black Tree
The production-default balanced BST: five color rules guarantee the longest path is at most twice the shortest, so height stays O(log n).
What to know
- Rules: nodes are red or black; root black; no red-red parent-child; equal black-height on every path.
- Insert fixes violations with recolors and at most two rotations.
- Delete is the hard case — "double black" resolution has four sub-cases.
In the wild: Java TreeMap, C++ std::map/set, Linux CFS run-queue, nginx timers.
Algorithms to reach for
Insert fix-up
O(log n)Restore color rules after insertion
Delete fix-up
O(log n)Restore black-height after removal
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.