Trees8 min read

Red-Black Tree

A self-balancing BST used inside Java's TreeMap and C++'s std::map
search: \(O(\log n)\)insert: \(O(\log n)\)delete: \(O(\log n)\)space: \(O(n)\)

A Red-Black tree is a self-balancing Binary Search Tree where every node carries one extra bit of information: its color — either red or black. This color system encodes balance constraints that ensure the tree never becomes too lopsided.

Red-Black trees power most real-world implementations of ordered maps and sets: java.util.TreeMap, C++'s std::map, Linux's CFS scheduler, and nginx's timer management all use Red-Black trees internally.

The five properties

Every valid Red-Black tree must satisfy all five of these properties simultaneously:

  1. Every node is either red or black.
  2. The root is always black.
  3. Every leaf (null sentinel node) is black.
  4. If a node is red, both its children must be black. (No two consecutive red nodes on any path.)
  5. All paths from any node to its descendant null leaves contain the same number of black nodes. This count is called the black-height.

Properties 4 and 5 together guarantee that the longest path from root to leaf is at most twice the shortest path. This keeps the tree "approximately balanced" and ensures \(O(\log n)\) operations.

◈ Explore red-black tree

← → arrow keys to step · click elements to interact

Red-Black Tree via Language Built-ins

# Python's sortedcontainers.SortedList uses a B-tree internally.
# For RB-tree semantics use a TreeMap equivalent: SortedList
from sortedcontainers import SortedList


sl = SortedList([5, 3, 8, 1, 4, 7, 9])
print(list(sl))            # [1, 3, 4, 5, 7, 8, 9]
sl.add(6)
sl.remove(3)
print(list(sl))            # [1, 4, 5, 6, 7, 8, 9]
print(sl[0], sl[-1])       # min=1, max=9
print(sl.bisect_left(6))   # index 3 (position of 6)
Output
[1, 3, 4, 5, 7, 8, 9]
[1, 4, 5, 6, 7, 8, 9]
1 9
3
Note: The longest path in a Red-Black tree (alternating red and black) is at most 2× the shortest path (all black). This looser balance guarantee compared to AVL means fewer rotations per insert/delete — which is why they're preferred in standard libraries.

Insertion in a Red-Black tree

New nodes are always inserted as red. This might violate property 4 (two consecutive red nodes). The fix involves one of these cases:

  • Uncle is red — Recolor parent and uncle to black, grandparent to red. Move the problem up the tree.
  • Uncle is black (triangle case) — Rotate the parent to make it a line.
  • Uncle is black (line case) — Rotate the grandparent and swap colors of parent and grandparent.

The recoloring and rotation cascade at most \(O(\log n)\) levels up the tree, maintaining \(O(\log n)\) total insertion cost.

Red-Black vs AVL: which to choose?

Both guarantee \(O(\log n)\) for all operations. The practical differences:

  • AVL trees are more strictly balanced (height ≤ 1.44 log n vs 2 log n for RB). Lookups are slightly faster. More rotations on insert/delete.
  • Red-Black trees do fewer rotations on insert and delete (at most 3 total, vs \(O(\log n)\) for AVL). Writes are faster. Used when insertions are frequent.

For most applications with mixed read/write workloads, Red-Black trees are preferred — which is why they dominate standard library implementations.

Black-height and guaranteed balance

The black-height of a tree is the number of black nodes on any path from root to leaf (not counting the root itself). Because all such paths have equal black-height (property 5), and because red nodes cannot be consecutive (property 4), the total height is bounded by 2 × black-height.

Complexity

SearchHeight ≤ 2 × \(\log_2(n+1)\)
Fast\(O(\log n)\)
InsertAt most 3 rotations + \(O(\log n)\) recoloring
Fast\(O(\log n)\)
DeleteMore complex than insert — up to 3 rotations
Fast\(O(\log n)\)
SpaceOne extra bit per node for color
Linear\(O(n)\)

Range Query on a Sorted Tree

from sortedcontainers import SortedList


sl = SortedList([10, 20, 30, 40, 50, 60, 70])


# Find all elements in range [25, 55]
lo = sl.bisect_left(25)
hi = sl.bisect_right(55)
print(list(sl[lo:hi]))  # [30, 40, 50]


# Count elements < 45
print(sl.bisect_left(45))  # 3
Output
[30, 40, 50]
3
Challenge

Quick check

What color is a newly inserted node in a Red-Black tree?

Continue reading

AVL Tree
A self-balancing BST that rebalances itself after every insert or delete
→
BST Balancing
An unbalanced BST is just a slow linked list in disguise
→
Binary Search Tree
A sorted binary tree — left is smaller, right is bigger
→