Home/Trees/Red-black tree
Search algorithmsCTRL K

Red-black tree

· self-balancing · recolour, then rotate
/trees/red-black-tree
NODES
1/ 12
in the tree
RECOLOURS
0
nodes repainted
ROTATIONS
0
so far
BLACK HEIGHT
1
black nodes root to leaf
HEIGHT
1
levels, root included
red nodeblack nodecurrentparent · uncle · grandparent
12 keys · seed 7 · 69 steps
step 0 / 68
Keys12
red_black_tree.ts
1
function insert(tree: Tree, key: number) {
2
  const node = bstInsert(tree, key); // new nodes are red
3
  fixUp(tree, node);
4
}
5
function fixUp(tree: Tree, node: Node) {
6
  while (node.parent?.color === "red") {
7
    const parent = node.parent, grandparent = parent.parent!;
8
    const uncle = parent === grandparent.left ? grandparent.right : grandparent.left;
9
    if (uncle?.color === "red") {
10
      parent.color = uncle.color = "black";
11
      grandparent.color = "red";
12
      node = grandparent;
13
      continue;
14
    }
15
    if (node === parent.right && parent === grandparent.left) { rotateLeft(tree, parent); node = parent; }
16
    else if (node === parent.left && parent === grandparent.right) { rotateRight(tree, parent); node = parent; }
17
    node.parent!.color = "black";
18
    grandparent.color = "red";
19
    if (node === node.parent!.left) rotateRight(tree, grandparent); else rotateLeft(tree, grandparent);
20
  }
21
  tree.root!.color = "black";
22
}
CURRENT STEP
line 21

The tree is empty: 24 becomes the root and is painted black.

// how it works

Understanding Red-black tree

red-black · two colours, five rules, no path twice as long as another
01

The idea

A red-black tree is a binary search tree where every node is red or black, the root is black, a red node never has a red child, and every path from the root to a leaf passes the same number of black nodes. Those rules force the longest path to be at most twice the shortest, so the height stays within 2 log₂ n.

A new node is inserted as a red leaf, which keeps the black count intact but may put two reds in a row. The fix-up looks at the uncle: if it is red, recolour parent, uncle and grandparent and move the problem two levels up; if it is black, one or two rotations plus a recolour fix it for good. Insertion therefore costs at most two rotations.

02

The four stages

1
insert reda red leaf keeps the black height
2
case 1red uncle: recolour, move up
3
case 2inner grandchild: rotate the parent
4
case 3recolour and rotate the grandparent
03

Complexity

best
O(log n)height ≤ 2 log₂(n + 1)
average
O(log n)insert: O(1) rotations amortised
worst
O(log n)guaranteed for every operation
space
O(n)one bit of colour per node
04

Versus its siblings

WORST HEIGHT · 1 000 000 KEYS
bst, random
60
bst, sorted
1M
avl
29
red-black
40
b-tree, order 128
3
a lookup costs one comparison per level
05

Pseudocode

INSERT(tree, key)
  node ← BST insert, coloured red
  while parent(node) is red
    if uncle(node) is red: paint parent and uncle black, grandparent red; node ← grandparent
    else: if node is an inner grandchild, rotate parent outward; paint parent black, grandparent red; rotate grandparent
  paint root black
06

When to use

General-purpose ordered maps and sets: C++ std::map, Java TreeMap, the Linux scheduler and memory maps all use it.
Insert- and delete-heavy workloads, where its fewer rotations beat AVL's stricter balance.
07

Pitfalls

Deletion has more cases than insertion and is where most hand-written implementations break.
Null leaves count as black; forgetting that breaks the uncle test at the edges.
Left-leaning red-black trees are simpler to code but not the same structure; do not mix the two sets of rules.
08

History

Rudolf Bayer invented the structure in 1972 as symmetric binary B-trees, a binary encoding of 2-3-4 trees. Leonidas Guibas and Robert Sedgewick gave it the red and black colours in 1978, chosen, Sedgewick says, because those were the pens that printed best on the laser printer at Xerox PARC.

Back to Trees