A red-black tree is a binary search tree that stays balanced by coloring every node red or black and enforcing a small set of rules about how those colors can appear. No node stores its height, and no strict height comparison drives rebalancing — the color rules alone guarantee that the longest path from root to leaf is never more than twice the shortest, which is enough to keep every operation at O(log n).
What changed in 2026
- It remains the default ordered container implementation across mainstream languages — C++
std::map/std::set, Java TreeMap/TreeSet — with no serious mainstream challenger displacing it for general-purpose in-memory ordered data.
- Explaining the five rules, not implementing rotations from memory, is now the more common interview ask, mirroring the broader shift toward tradeoff reasoning over rote implementation.
- Visualizers that animate rotations and recoloring live in the browser have made the rules far easier to build intuition for than static diagrams alone.
The five rules that keep it balanced
- Every node is colored red or black.
- The root is always black.
- Every null leaf is treated as black.
- A red node cannot have a red child — no two reds in a row on any path.
- Every path from a node to any of its descendant null leaves passes through the same number of black nodes.
Together, these rules bound the height at roughly 2 × log2(n), looser than a perfectly balanced tree but cheap to maintain.
Rotations and recoloring, briefly
Insertion starts like a normal BST insert, coloring the new node red, then walks back up fixing any rule-4 violations through a bounded sequence of recolors and rotations.
def rotate_left(tree, x):
y = x.right
x.right = y.left
if y.left:
y.left.parent = x
y.parent = x.parent
if not x.parent:
tree.root = y
elif x is x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
A right rotation is the mirror image. Fixing a violation takes at most a small constant number of rotations plus O(log n) recolors up the path to the root.
Red-black tree vs AVL tree vs B-tree
| Property |
Red-black tree |
AVL tree |
B-tree |
| Balance guarantee |
Height ≤ ~2 log2(n) |
Height ≤ ~1.44 log2(n) |
Balanced, wide and shallow |
| Rebalancing cost |
Small, bounded per insert/delete |
Can cascade up to O(log n) rotations |
Node splits/merges, not rotations |
| Lookup speed |
Slightly slower than AVL |
Fastest of the two BSTs |
Very fast per level, few levels total |
| Best for |
Frequent inserts and deletes, in-memory |
Read-heavy workloads, in-memory |
Disk or SSD-backed storage |
See what is an AVL tree for the tighter-balance alternative, and what is a B-tree for why databases use a different shape entirely.
Where red-black trees actually show up
C++ std::map and std::set, Java TreeMap and TreeSet, and process scheduling and virtual memory management inside the Linux kernel all use red-black trees internally. Any ordered map used in a mainstream language has a good chance of being balanced by a red-black tree underneath it.
Common pitfalls
Implementing rotations and recoloring from scratch in production. It is easy to get subtly wrong; the ordered container in a standard library has already had this logic tested for years.
Assuming a red-black tree beats a hash map. It does not, for plain lookups — hash maps average O(1), red-black trees guarantee O(log n). Reach for the tree only when ordering or range queries matter.
Forgetting that null leaves count as black. Hand-verifying the black-height rule without counting null leaves gives the wrong answer.
FAQ
Why not just use an AVL tree instead?
AVL trees are more tightly balanced, so lookups are marginally faster, but they rebalance more aggressively on insert and delete. Red-black trees favor cheaper writes at the cost of a slightly taller tree.
Do I ever need to implement one myself?
Rarely in application code. Understanding the rules helps reason about the guarantees of the ordered containers already in use, not necessarily re-implement them.
How is this different from a B-tree?
A red-black tree is a binary tree, at most two children per node, tuned for in-memory access. A B-tree is a multi-way tree with many children per node, tuned to minimize disk reads, which is why databases use B-trees for on-disk indexes instead.
What is black-height?
The number of black nodes on any path from a node down to a leaf, not counting the node itself. Rule five guarantees this count is identical for every path from a given node.
Where to go next