Red-black tree

A red-black tree is a self-balancing Binary search tree that uses node colors (red or black) instead of explicit balance factors to maintain balance. The balancing rules are looser than AVL’s, leading to slightly faster insertions/deletions at the cost of slightly slower searches. Used in the C++ STL std::map, the Linux kernel scheduler, and Java’s TreeMap.

The five properties

Every red-black tree must satisfy:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (the conceptual NIL/null nodes) is black.
4. Red nodes can’t have red children. (No two consecutive reds on any path.)
5. Every path from a node to its descendant NIL nodes contains the same number of black nodes.

Property 4 (no consecutive reds) plus property 5 (equal black-counts) together imply the tree is roughly balanced: the longest path is at most twice the length of the shortest path. So the height is $O(\log n)$.

Image: Example red-black tree, CC BY-SA 3.0 — black root, red/black internal nodes, and the explicit black NIL leaves.

Why colors

The colors are just bookkeeping — bits attached to each node. They encode enough information about local structure to drive rebalancing decisions without needing to compute heights.

In contrast, AVL trees track exact heights (or balance factors), which is more precise but requires more updates per operation.

Insertion

Rules for inserting:

1. Insert the new node like a regular BST, colored red.
2. If the new node is the root, recolor it black (preserves property 2). Done.
3. If the parent is black, no rule is violated. Done.
4. If the parent is red (violating property 4), fix-up:
   • Case A: uncle is red. Recolor parent and uncle to black, grandparent to red. Then recurse on grandparent (might cause a new red-red violation higher up).
   • Case B: uncle is black. Rotate and/or recolor to fix locally.

The uncle is the sibling of the parent.

The algorithm is a bit fiddly in detail, but the high-level idea is: insert red (which doesn’t change black-count), then either recolor or rotate to fix up any red-red conflicts.

Deletion

More complex than insertion. The cases:

1. Find the node to delete.
2. If the node has two children, replace its value with its in-order successor (same as plain BST deletion).
3. The remaining structural deletion involves at most one node with at most one child.
4. If the deleted node or its replacement is red, just remove it (no black-count violation). Done.
5. If both are black, you’ve reduced the black-count on one path → “double black” issue. Fix up:
   • If the sibling is black with a red child: rotate and recolor.
   • If the sibling is black with two black children: recolor and propagate the problem upward.
   • If the sibling is red: rotate to convert to one of the previous cases.

Like insertion, the cases handle local structural fixes; sometimes the fix has to bubble up.

Compared to AVL

Property	AVL	Red-black
Maximum height	$\approx 1.44\log n$	$\approx 2\log n$
Search speed	Slightly faster (shorter paths)	Slightly slower
Insert: total rebalancing work	More (recolorings + rotations farther up)	Less
Insert: rotations per op	$\le 2$	$\le 2$
Delete: total rebalancing work	More	Less
Implementation complexity	Moderate	More complex

Both AVL and red-black do at most $O(1)$ literal rotations per insertion (at most 2 in either case). The “faster insert” of red-black isn’t about rotation count per insert; it’s about total rebalancing work — AVL’s tighter balance condition means rebalancing is more sensitive and propagates further up the tree on average, costing more total recoloring/rotation work even when the per-event rotation count matches. Both achieve $O(\log n)$ for all operations. The choice between them is usually driven by use case:

• Mostly searches: AVL.
• Mix of inserts/deletes: red-black.
• Strict latency requirements (worst-case bound on rotations per operation): red-black gives a constant bound on insertion fix-ups (≤ 2 rotations), while AVL guarantees ≤ 2 rotations per insertion but can do $O(\log n)$ rotations on deletion.

In practice, red-black trees are more common in production systems because of their better insert/delete performance and their stricter worst-case bounds on rebalancing work.

Worked insertion example

Start with an empty tree. Insert 10, 20, 30, 15, 25 in that order. Writing each node as value(color):

• Insert 10: new node, colored red; it’s the root, so recolor black. Tree: 10(B).
• Insert 20: new red node, parent 10 is black — no violation. 20(R) is the right child of 10(B).
• Insert 30: new red node 30, parent 20 is red — violation; 30’s uncle is NIL (black), a “right-right” structure. Fix by left-rotating at grandparent 10 and recoloring: 20(B) is now root with children 10(R) and 30(R).
• Insert 15: new red node, parent 10 is red — violation; uncle 30 is red, so recolor parent 10 and uncle 30 to black and grandparent 20 to red; 20 is the root so recolor it back to black. Tree: root 20(B), children 10(B) and 30(B), with 15(R) as the right child of 10.
• Insert 25: new red node, parent 30 is black — no violation. 25(R) is the left child of 30. Final tree: root 20(B); left subtree 10(B) with right child 15(R); right subtree 30(B) with left child 25(R).

The tree stays balanced. Both insertion and lookup are $O(\log n)$.

Worked deletion example

Continuing from the tree above, delete node 30.

30 has one child (25, red). Replace 30 with 25 and color 25 black. Result: root 20(B), children 10(B) and 25(B), with 15(R) as the right child of 10. Done — no black-count violation, since the replacement is now black.

If we had instead deleted 10 (one child, 15 red): replace 10 with 15 and color 15 black. Result: root 20(B), children 15(B) and 30(B), with 25(R) as the left child of 30. Still balanced.

If we had deleted a black node with no red child to promote (a “double-black” situation), the fix-up cases mentioned earlier would kick in — rotating and recoloring siblings until the black-count is restored.

The full deletion algorithm has 8+ cases in some variants, but production implementations (in std libraries) handle them in ~50 lines of code.

Why production code uses red-black

Despite being more complex than AVL, red-black trees are preferred in industrial code because:

1. Constant rotations per modification: at most 2 rotations per insertion and ≤ 3 per deletion. AVL also caps insertions at ≤ 2 rotations, but its deletion can require $O(\log n)$ rotations as rebalancing propagates up.
2. Better cache behavior: looser balancing means slightly more flexible memory layout.
3. Easier bulk operations: merging, splitting trees is simpler.

This is why C++ STL std::map / std::set, Java’s TreeMap / TreeSet, and the Linux kernel’s process scheduler all use red-black trees.

Further reading

For visual exploration of insertions and deletions, the USFCA visualization is excellent.

For the simpler self-balancing alternative, see AVL tree. For the un-balanced baseline, see Binary search tree.