Red-Black Trees

A red-black tree is a self-balancing binary search tree that uses node colours and five rules to keep height within a factor of two of optimal.

Colours as a balance proxy

A red-black tree is a binary search tree where each node is coloured red or black. Rather than tracking exact heights like an AVL tree, it enforces colour rules that keep the longest root-to-leaf path at most twice the shortest, which bounds height at about 2 log n and every operation at O(log n).

The five rules

• Every node is red or black
• The root is black
• Red nodes may not have red children (no two reds in a row)
• Every root-to-null path has the same number of black nodes
• Null leaves count as black

Repair by recolour and rotate

A new node is inserted red. If its parent is also red, the fourth-and-third rules are violated and the tree repairs itself by recolouring nodes or performing a rotation, working up toward the root. Deletion is more intricate, tracking a doubly-black condition that propagates upward until it can be resolved. Both operations do at most a constant number of rotations.

Why looser balance helps writes

Because red-black trees tolerate more imbalance than AVL trees, they perform fewer rotations during insertion and deletion. That makes them attractive when the workload is write-heavy, at the cost of slightly taller trees and marginally slower lookups.

Where they run

Red-black trees are the workhorse behind many standard-library ordered containers, including the maps and sets in the C++ and Java standard libraries, and they appear inside operating-system schedulers. They are chosen for a dependable O(log n) worst case with modest rebalancing overhead across mixed read and write workloads.