PK

PKBytes

Explore tracks
Chapter 26: Self-Balancing Search Trees and B-Trees
26.02Intermediate / Advanced7 topics20 min5 interactive animations

Red-black trees

Red-black trees: the colour rules, black height, rotations, the insertion and deletion fix-ups, the guaranteed properties and how Java's TreeMap uses them.

Learning goals

  • State the red-black rules and the black-height invariant
  • Follow the three insertion cases and the four deletion cases
  • Explain why the height is at most 2 log2(n + 1)
  • Recognise a red-black tree inside Java's TreeMap and TreeSet

Prerequisites

AVL trees

AVL trees keep a strict balance at the price of many rotations. A red-black tree relaxes the rule, balancing by colours, and needs fewer rotations per update, which is why most library maps use it.

26.02.1

Node colors

Every node is **red** or **black**, and these rules hold: (1) the root is black; (2) every empty child (NIL) counts as black; (3) a red node has no red child; (4) every path from a node down to a NIL has the same number of black nodes. A newly inserted node is coloured red, because that changes no path's black count.

In the animation red nodes are shaded rose and black ones grey, and the label under each node spells the colour. Rule (3) bounds how bad a path can be: a red node must be followed by a black one, so paths can differ in length by at most a factor of two.

Red-black tree: insertion and deletion fix-ups

Interactive · edit the input

Your input

Try
Setup

A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.

Step 1 / 17
Java
1static final int RED = 0, BLACK = 1;
2static class Node { int key, color = RED; Node left, right, parent; Node(int k) { key = k; } }
3static final Node NIL = new Node(0);             // one shared black sentinel stands for every empty child
4static Node root = NIL;
5static void rotateLeft(Node x) {
6    Node y = x.right;
7    x.right = y.left;
8    if (y.left != NIL) y.left.parent = x;
9    y.parent = x.parent;
10    if (x.parent == NIL) root = y;
11    else if (x == x.parent.left) x.parent.left = y;
12    else x.parent.right = y;
13    y.left = x;
14    x.parent = y;
15}                                                // rotateRight is the mirror image
16static void fixInsert(Node z) {                  // z is red; only "red parent" can be violated
17    while (z.parent.color == RED) {
18        Node g = z.parent.parent;
19        Node uncle = z.parent == g.left ? g.right : g.left;
20        if (uncle.color == RED) {                // case 1: recolor and move up
21            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
22            z = g;
23        } else if (z.parent == g.left) {
24            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }   // case 2: straighten the bend
25            z.parent.color = BLACK; g.color = RED;                       // case 3: rotate the grandparent
26            rotateRight(g);
27        } else {                                 // mirror image on the right side
28            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
29            z.parent.color = BLACK; g.color = RED;
30            rotateLeft(g);
31        }
32    }
33    root.color = BLACK;
34}
35static void fixDelete(Node x) {                  // x carries an extra black
36    while (x != root && x.color == BLACK) {
37        boolean left = x == x.parent.left;
38        Node w = left ? x.parent.right : x.parent.left;               // sibling
39        if (w.color == RED) {                    // case 1: red sibling, rotate it to the top
40            w.color = BLACK; x.parent.color = RED;
41            if (left) rotateLeft(x.parent); else rotateRight(x.parent);
42        } else if (w.left.color == BLACK && w.right.color == BLACK) {  // case 2: push the extra black up
43            w.color = RED;
44            x = x.parent;
45        } else {
46            // cases 3 and 4: a red nephew lets rotations fix the black height
47        }
48    }
49    x.color = BLACK;
50}

Live state

0 rotations0 recolorings

black height

0

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1black height=0A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.
2L32black height=0 inserted=10Insert 10 as a red leaf (the root). Red keeps the black height unchanged; the only possible violation is a red parent.
3L33black height=1The root must be black: recolor 10 black.
4L32black height=1 inserted=20Insert 20 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
5L32black height=1 inserted=30Insert 30 as a red leaf, below 20. Red keeps the black height unchanged; the only possible violation is a red parent.
6L25black height=1 case=3The uncle is black and the nodes form a straight line (case 3): color the parent 20 black and the grandparent 10 red, then rotate 10 left.
7L26black height=1 case=3Rotated: 20 is now the root of this subtree, with the red children 10 and 30. The fix-up is finished.
8L32black height=1 inserted=15Insert 15 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
9L21black height=1 case=1Parent 10 and uncle 30 are both red (case 1): recolor them black and the grandparent 20 red, then continue from 20.
10L22black height=1 case=1Recolored. 20 is now red; check whether its own parent is red.
11L33black height=2The root must be black: recolor 20 black.
12L32black height=2 inserted=25Insert 25 as a red leaf, below 30. Red keeps the black height unchanged; the only possible violation is a red parent.
13L32black height=2 inserted=5Insert 5 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
14L32black height=2 inserted=1Insert 1 as a red leaf, below 5. Red keeps the black height unchanged; the only possible violation is a red parent.
15L21black height=2 case=1Parent 5 and uncle 15 are both red (case 1): recolor them black and the grandparent 10 red, then continue from 10.
16L22black height=2 case=1Recolored. 10 is now red; check whether its own parent is red.
17L33keys=7 height=3 black height=27 keys, height 3, black height 2. 1 rotation and 10 recolorings in total. The longest path can be at most twice the shortest, so the height stays O(log n).
26.02.2

Black-height

The **black height** of a node is the number of black nodes on any path from it down to a NIL, not counting the node itself in some books. Rule (4) says it is well defined: all such paths agree. The animation's result line reports it for the whole tree.

A node of black height b has at least 2^b - 1 nodes in its subtree (the shortest path is all black, and then the tree is complete down to that level). Since red nodes never occur twice in a row, the black height of the root is at least half the height, so n >= 2^(h/2) - 1, which gives h <= 2 log2(n + 1). The “Sorted input” preset, 1 to 7 inserted in order, ends at height 3 with black height 2.

QuantityBound
Nodes in a subtree of black height bat least 2^b - 1
Longest path / shortest pathat most 2
Height of a tree with n nodesat most 2 log2(n + 1)

Red-black tree: insertion and deletion fix-ups

Interactive · edit the input

Your input

Try
Setup

A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.

Step 1 / 17
Java
1static final int RED = 0, BLACK = 1;
2static class Node { int key, color = RED; Node left, right, parent; Node(int k) { key = k; } }
3static final Node NIL = new Node(0);             // one shared black sentinel stands for every empty child
4static Node root = NIL;
5static void rotateLeft(Node x) {
6    Node y = x.right;
7    x.right = y.left;
8    if (y.left != NIL) y.left.parent = x;
9    y.parent = x.parent;
10    if (x.parent == NIL) root = y;
11    else if (x == x.parent.left) x.parent.left = y;
12    else x.parent.right = y;
13    y.left = x;
14    x.parent = y;
15}                                                // rotateRight is the mirror image
16static void fixInsert(Node z) {                  // z is red; only "red parent" can be violated
17    while (z.parent.color == RED) {
18        Node g = z.parent.parent;
19        Node uncle = z.parent == g.left ? g.right : g.left;
20        if (uncle.color == RED) {                // case 1: recolor and move up
21            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
22            z = g;
23        } else if (z.parent == g.left) {
24            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }   // case 2: straighten the bend
25            z.parent.color = BLACK; g.color = RED;                       // case 3: rotate the grandparent
26            rotateRight(g);
27        } else {                                 // mirror image on the right side
28            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
29            z.parent.color = BLACK; g.color = RED;
30            rotateLeft(g);
31        }
32    }
33    root.color = BLACK;
34}
35static void fixDelete(Node x) {                  // x carries an extra black
36    while (x != root && x.color == BLACK) {
37        boolean left = x == x.parent.left;
38        Node w = left ? x.parent.right : x.parent.left;               // sibling
39        if (w.color == RED) {                    // case 1: red sibling, rotate it to the top
40            w.color = BLACK; x.parent.color = RED;
41            if (left) rotateLeft(x.parent); else rotateRight(x.parent);
42        } else if (w.left.color == BLACK && w.right.color == BLACK) {  // case 2: push the extra black up
43            w.color = RED;
44            x = x.parent;
45        } else {
46            // cases 3 and 4: a red nephew lets rotations fix the black height
47        }
48    }
49    x.color = BLACK;
50}

Live state

0 rotations0 recolorings

black height

0

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1black height=0A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.
2L32black height=0 inserted=10Insert 10 as a red leaf (the root). Red keeps the black height unchanged; the only possible violation is a red parent.
3L33black height=1The root must be black: recolor 10 black.
4L32black height=1 inserted=20Insert 20 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
5L32black height=1 inserted=30Insert 30 as a red leaf, below 20. Red keeps the black height unchanged; the only possible violation is a red parent.
6L25black height=1 case=3The uncle is black and the nodes form a straight line (case 3): color the parent 20 black and the grandparent 10 red, then rotate 10 left.
7L26black height=1 case=3Rotated: 20 is now the root of this subtree, with the red children 10 and 30. The fix-up is finished.
8L32black height=1 inserted=15Insert 15 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
9L21black height=1 case=1Parent 10 and uncle 30 are both red (case 1): recolor them black and the grandparent 20 red, then continue from 20.
10L22black height=1 case=1Recolored. 20 is now red; check whether its own parent is red.
11L33black height=2The root must be black: recolor 20 black.
12L32black height=2 inserted=25Insert 25 as a red leaf, below 30. Red keeps the black height unchanged; the only possible violation is a red parent.
13L32black height=2 inserted=5Insert 5 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
14L32black height=2 inserted=1Insert 1 as a red leaf, below 5. Red keeps the black height unchanged; the only possible violation is a red parent.
15L21black height=2 case=1Parent 5 and uncle 15 are both red (case 1): recolor them black and the grandparent 10 red, then continue from 10.
16L22black height=2 case=1Recolored. 10 is now red; check whether its own parent is red.
17L33keys=7 height=3 black height=27 keys, height 3, black height 2. 1 rotation and 10 recolorings in total. The longest path can be at most twice the shortest, so the height stays O(log n).
26.02.3

Rotations

Red-black trees use the same rotations as AVL trees; only the bookkeeping differs. A rotation never changes the order of the keys, and here it must keep the parent pointers right, because the fix-up algorithms walk upward. The tree uses a single shared black **NIL** sentinel for every empty child, which removes the null checks from the fix-up code.

Rotate left around x: x's right child y takes x's place, x becomes y's left child, and y's old left subtree becomes x's right subtree. Rotate right is the mirror image.

Java
1static final int RED = 0, BLACK = 1;
2static class Node {
3    int key, color = RED;
4    Node left, right, parent;
5    Node(int key) { this.key = key; }
6}
7static Node nil() { Node n = new Node(0); n.color = BLACK; n.left = n; n.right = n; n.parent = n; return n; }
8static final Node NIL = nil();                   // one black sentinel stands for every empty child
9static Node root = NIL;
10
11static void rotateLeft(Node x) {
12    Node y = x.right;
13    x.right = y.left;
14    if (y.left != NIL) y.left.parent = x;
15    y.parent = x.parent;
16    if (x.parent == NIL) root = y;
17    else if (x == x.parent.left) x.parent.left = y;
18    else x.parent.right = y;
19    y.left = x;
20    x.parent = y;
21}
22static void rotateRight(Node y) {
23    Node x = y.left;
24    y.left = x.right;
25    if (x.right != NIL) x.right.parent = y;
26    x.parent = y.parent;
27    if (y.parent == NIL) root = x;
28    else if (y == y.parent.right) y.parent.right = x;
29    else y.parent.left = x;
30    x.right = y;
31    y.parent = x;
32}

Red-black tree: insertion and deletion fix-ups

Interactive · edit the input

Your input

Try
Setup

A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.

Step 1 / 17
Java
1static final int RED = 0, BLACK = 1;
2static class Node { int key, color = RED; Node left, right, parent; Node(int k) { key = k; } }
3static final Node NIL = new Node(0);             // one shared black sentinel stands for every empty child
4static Node root = NIL;
5static void rotateLeft(Node x) {
6    Node y = x.right;
7    x.right = y.left;
8    if (y.left != NIL) y.left.parent = x;
9    y.parent = x.parent;
10    if (x.parent == NIL) root = y;
11    else if (x == x.parent.left) x.parent.left = y;
12    else x.parent.right = y;
13    y.left = x;
14    x.parent = y;
15}                                                // rotateRight is the mirror image
16static void fixInsert(Node z) {                  // z is red; only "red parent" can be violated
17    while (z.parent.color == RED) {
18        Node g = z.parent.parent;
19        Node uncle = z.parent == g.left ? g.right : g.left;
20        if (uncle.color == RED) {                // case 1: recolor and move up
21            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
22            z = g;
23        } else if (z.parent == g.left) {
24            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }   // case 2: straighten the bend
25            z.parent.color = BLACK; g.color = RED;                       // case 3: rotate the grandparent
26            rotateRight(g);
27        } else {                                 // mirror image on the right side
28            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
29            z.parent.color = BLACK; g.color = RED;
30            rotateLeft(g);
31        }
32    }
33    root.color = BLACK;
34}
35static void fixDelete(Node x) {                  // x carries an extra black
36    while (x != root && x.color == BLACK) {
37        boolean left = x == x.parent.left;
38        Node w = left ? x.parent.right : x.parent.left;               // sibling
39        if (w.color == RED) {                    // case 1: red sibling, rotate it to the top
40            w.color = BLACK; x.parent.color = RED;
41            if (left) rotateLeft(x.parent); else rotateRight(x.parent);
42        } else if (w.left.color == BLACK && w.right.color == BLACK) {  // case 2: push the extra black up
43            w.color = RED;
44            x = x.parent;
45        } else {
46            // cases 3 and 4: a red nephew lets rotations fix the black height
47        }
48    }
49    x.color = BLACK;
50}

Live state

0 rotations0 recolorings

black height

0

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1black height=0A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.
2L32black height=0 inserted=10Insert 10 as a red leaf (the root). Red keeps the black height unchanged; the only possible violation is a red parent.
3L33black height=1The root must be black: recolor 10 black.
4L32black height=1 inserted=20Insert 20 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
5L32black height=1 inserted=30Insert 30 as a red leaf, below 20. Red keeps the black height unchanged; the only possible violation is a red parent.
6L25black height=1 case=3The uncle is black and the nodes form a straight line (case 3): color the parent 20 black and the grandparent 10 red, then rotate 10 left.
7L26black height=1 case=3Rotated: 20 is now the root of this subtree, with the red children 10 and 30. The fix-up is finished.
8L32black height=1 inserted=15Insert 15 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
9L21black height=1 case=1Parent 10 and uncle 30 are both red (case 1): recolor them black and the grandparent 20 red, then continue from 20.
10L22black height=1 case=1Recolored. 20 is now red; check whether its own parent is red.
11L33black height=2The root must be black: recolor 20 black.
12L32black height=2 inserted=25Insert 25 as a red leaf, below 30. Red keeps the black height unchanged; the only possible violation is a red parent.
13L32black height=2 inserted=5Insert 5 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
14L32black height=2 inserted=1Insert 1 as a red leaf, below 5. Red keeps the black height unchanged; the only possible violation is a red parent.
15L21black height=2 case=1Parent 5 and uncle 15 are both red (case 1): recolor them black and the grandparent 10 red, then continue from 10.
16L22black height=2 case=1Recolored. 10 is now red; check whether its own parent is red.
17L33keys=7 height=3 black height=27 keys, height 3, black height 2. 1 rotation and 10 recolorings in total. The longest path can be at most twice the shortest, so the height stays O(log n).
26.02.4

Insert fix-up

Insert like a BST and colour the new node **red**. The only rule that can break is 'no red node has a red child', and only if the parent is red. Look at the **uncle** (the parent's sibling). **Case 1, red uncle**: recolor the parent and uncle black and the grandparent red, then repeat from the grandparent. **Case 2, black uncle and a bend** (z is an inner child): rotate the parent so the nodes form a straight line. **Case 3, black uncle and a straight line**: recolor the parent black and the grandparent red, and rotate the grandparent. Finally the root is coloured black.

Presets: inserting 10, 20, 30 is case 3 (1 rotation); 10, 30, 20 is cases 2 then 3 (2 rotations); 20, 10, 30, 5 is case 1 with no rotations. Cases 2 and 3 end the fix-up; case 1 may repeat up the tree, but a single insertion never needs more than two rotations.

Java
1static void insert(int key) {
2    Node z = new Node(key);
3    z.left = NIL; z.right = NIL;
4    Node p = NIL, cur = root;
5    while (cur != NIL) { p = cur; cur = key < cur.key ? cur.left : cur.right; }
6    z.parent = p;
7    if (p == NIL) root = z;
8    else if (key < p.key) p.left = z;
9    else p.right = z;                            // the new node is red
10    fixInsert(z);
11}
12static void fixInsert(Node z) {
13    while (z.parent.color == RED) {              // a red parent breaks the "no red-red" rule
14        Node g = z.parent.parent;
15        Node uncle = z.parent == g.left ? g.right : g.left;
16        if (uncle.color == RED) {                // case 1: recolor and continue from the grandparent
17            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
18            z = g;
19        } else if (z.parent == g.left) {
20            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }      // case 2: straighten the bend
21            z.parent.color = BLACK; g.color = RED;                          // case 3: recolor, rotate the grandparent
22            rotateRight(g);
23        } else {                                 // mirror image
24            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
25            z.parent.color = BLACK; g.color = RED;
26            rotateLeft(g);
27        }
28    }
29    root.color = BLACK;
30}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1) beyond the search

Red-black tree: insertion and deletion fix-ups

Interactive · edit the input

Your input

Try
Setup

A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.

Step 1 / 17
Java
1static final int RED = 0, BLACK = 1;
2static class Node { int key, color = RED; Node left, right, parent; Node(int k) { key = k; } }
3static final Node NIL = new Node(0);             // one shared black sentinel stands for every empty child
4static Node root = NIL;
5static void rotateLeft(Node x) {
6    Node y = x.right;
7    x.right = y.left;
8    if (y.left != NIL) y.left.parent = x;
9    y.parent = x.parent;
10    if (x.parent == NIL) root = y;
11    else if (x == x.parent.left) x.parent.left = y;
12    else x.parent.right = y;
13    y.left = x;
14    x.parent = y;
15}                                                // rotateRight is the mirror image
16static void fixInsert(Node z) {                  // z is red; only "red parent" can be violated
17    while (z.parent.color == RED) {
18        Node g = z.parent.parent;
19        Node uncle = z.parent == g.left ? g.right : g.left;
20        if (uncle.color == RED) {                // case 1: recolor and move up
21            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
22            z = g;
23        } else if (z.parent == g.left) {
24            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }   // case 2: straighten the bend
25            z.parent.color = BLACK; g.color = RED;                       // case 3: rotate the grandparent
26            rotateRight(g);
27        } else {                                 // mirror image on the right side
28            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
29            z.parent.color = BLACK; g.color = RED;
30            rotateLeft(g);
31        }
32    }
33    root.color = BLACK;
34}
35static void fixDelete(Node x) {                  // x carries an extra black
36    while (x != root && x.color == BLACK) {
37        boolean left = x == x.parent.left;
38        Node w = left ? x.parent.right : x.parent.left;               // sibling
39        if (w.color == RED) {                    // case 1: red sibling, rotate it to the top
40            w.color = BLACK; x.parent.color = RED;
41            if (left) rotateLeft(x.parent); else rotateRight(x.parent);
42        } else if (w.left.color == BLACK && w.right.color == BLACK) {  // case 2: push the extra black up
43            w.color = RED;
44            x = x.parent;
45        } else {
46            // cases 3 and 4: a red nephew lets rotations fix the black height
47        }
48    }
49    x.color = BLACK;
50}

Live state

0 rotations0 recolorings

black height

0

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1black height=0A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.
2L32black height=0 inserted=10Insert 10 as a red leaf (the root). Red keeps the black height unchanged; the only possible violation is a red parent.
3L33black height=1The root must be black: recolor 10 black.
4L32black height=1 inserted=20Insert 20 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
5L32black height=1 inserted=30Insert 30 as a red leaf, below 20. Red keeps the black height unchanged; the only possible violation is a red parent.
6L25black height=1 case=3The uncle is black and the nodes form a straight line (case 3): color the parent 20 black and the grandparent 10 red, then rotate 10 left.
7L26black height=1 case=3Rotated: 20 is now the root of this subtree, with the red children 10 and 30. The fix-up is finished.
8L32black height=1 inserted=15Insert 15 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
9L21black height=1 case=1Parent 10 and uncle 30 are both red (case 1): recolor them black and the grandparent 20 red, then continue from 20.
10L22black height=1 case=1Recolored. 20 is now red; check whether its own parent is red.
11L33black height=2The root must be black: recolor 20 black.
12L32black height=2 inserted=25Insert 25 as a red leaf, below 30. Red keeps the black height unchanged; the only possible violation is a red parent.
13L32black height=2 inserted=5Insert 5 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
14L32black height=2 inserted=1Insert 1 as a red leaf, below 5. Red keeps the black height unchanged; the only possible violation is a red parent.
15L21black height=2 case=1Parent 5 and uncle 15 are both red (case 1): recolor them black and the grandparent 10 red, then continue from 10.
16L22black height=2 case=1Recolored. 10 is now red; check whether its own parent is red.
17L33keys=7 height=3 black height=27 keys, height 3, black height 2. 1 rotation and 10 recolorings in total. The longest path can be at most twice the shortest, so the height stays O(log n).
26.02.5

Delete fix-up

Deletion is the BST deletion with a **transplant** (the successor takes the deleted node's place and colour). If the node that physically left the tree was **red**, nothing breaks. If it was **black**, one black node is missing on the paths through its position, and the node x that took its place carries an extra 'double black'. The fix-up looks at the sibling w. **Case 1**: w is red: recolor and rotate so the sibling is black. **Case 2**: w and both its children are black: colour w red and push the extra black up to the parent. **Case 3**: w is black with a red near child and a black far child: rotate w to move the red child to the far side. **Case 4**: w is black with a red far child: recolor and rotate the parent; the extra black is gone.

The “Delete a red leaf” preset needs no fix-up. The “Delete a black leaf (double black)” preset builds 20, 10, 30, 5 and deletes 30: the sibling 10 is black with a red far child 5, which is case 4 and ends with one rotation. Deleting needs at most 3 rotations.

Java
1static void transplant(Node u, Node v) {
2    if (u.parent == NIL) root = v;
3    else if (u == u.parent.left) u.parent.left = v;
4    else u.parent.right = v;
5    v.parent = u.parent;                         // also valid for v == NIL: the fix-up needs it
6}
7static Node minimum(Node n) { while (n.left != NIL) n = n.left; return n; }
8static void delete(Node z) {
9    Node y = z, x;
10    int yColor = y.color;
11    if (z.left == NIL) { x = z.right; transplant(z, z.right); }
12    else if (z.right == NIL) { x = z.left; transplant(z, z.left); }
13    else {
14        y = minimum(z.right);                    // the successor takes z's place and colour
15        yColor = y.color;
16        x = y.right;
17        if (y.parent == z) x.parent = y;
18        else { transplant(y, y.right); y.right = z.right; y.right.parent = y; }
19        transplant(z, y);
20        y.left = z.left; y.left.parent = y;
21        y.color = z.color;
22    }
23    if (yColor == BLACK) fixDelete(x);           // a black node left: one black is missing
24}
25static void fixDelete(Node x) {
26    while (x != root && x.color == BLACK) {
27        if (x == x.parent.left) {
28            Node w = x.parent.right;
29            if (w.color == RED) { w.color = BLACK; x.parent.color = RED; rotateLeft(x.parent); w = x.parent.right; }   // case 1
30            if (w.left.color == BLACK && w.right.color == BLACK) { w.color = RED; x = x.parent; }                     // case 2
31            else {
32                if (w.right.color == BLACK) { w.left.color = BLACK; w.color = RED; rotateRight(w); w = x.parent.right; }   // case 3
33                w.color = x.parent.color; x.parent.color = BLACK; w.right.color = BLACK;                                     // case 4
34                rotateLeft(x.parent);
35                x = root;
36            }
37        } else {
38            Node w = x.parent.left;
39            if (w.color == RED) { w.color = BLACK; x.parent.color = RED; rotateRight(x.parent); w = x.parent.left; }
40            if (w.right.color == BLACK && w.left.color == BLACK) { w.color = RED; x = x.parent; }
41            else {
42                if (w.left.color == BLACK) { w.right.color = BLACK; w.color = RED; rotateLeft(w); w = x.parent.left; }
43                w.color = x.parent.color; x.parent.color = BLACK; w.left.color = BLACK;
44                rotateRight(x.parent);
45                x = root;
46            }
47        }
48    }
49    x.color = BLACK;
50}

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1) beyond the search

Red-black tree: insertion and deletion fix-ups

Interactive · edit the input

Your input

Try
Setup

A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.

Step 1 / 17
Java
1static final int RED = 0, BLACK = 1;
2static class Node { int key, color = RED; Node left, right, parent; Node(int k) { key = k; } }
3static final Node NIL = new Node(0);             // one shared black sentinel stands for every empty child
4static Node root = NIL;
5static void rotateLeft(Node x) {
6    Node y = x.right;
7    x.right = y.left;
8    if (y.left != NIL) y.left.parent = x;
9    y.parent = x.parent;
10    if (x.parent == NIL) root = y;
11    else if (x == x.parent.left) x.parent.left = y;
12    else x.parent.right = y;
13    y.left = x;
14    x.parent = y;
15}                                                // rotateRight is the mirror image
16static void fixInsert(Node z) {                  // z is red; only "red parent" can be violated
17    while (z.parent.color == RED) {
18        Node g = z.parent.parent;
19        Node uncle = z.parent == g.left ? g.right : g.left;
20        if (uncle.color == RED) {                // case 1: recolor and move up
21            z.parent.color = BLACK; uncle.color = BLACK; g.color = RED;
22            z = g;
23        } else if (z.parent == g.left) {
24            if (z == z.parent.right) { z = z.parent; rotateLeft(z); }   // case 2: straighten the bend
25            z.parent.color = BLACK; g.color = RED;                       // case 3: rotate the grandparent
26            rotateRight(g);
27        } else {                                 // mirror image on the right side
28            if (z == z.parent.left) { z = z.parent; rotateRight(z); }
29            z.parent.color = BLACK; g.color = RED;
30            rotateLeft(g);
31        }
32    }
33    root.color = BLACK;
34}
35static void fixDelete(Node x) {                  // x carries an extra black
36    while (x != root && x.color == BLACK) {
37        boolean left = x == x.parent.left;
38        Node w = left ? x.parent.right : x.parent.left;               // sibling
39        if (w.color == RED) {                    // case 1: red sibling, rotate it to the top
40            w.color = BLACK; x.parent.color = RED;
41            if (left) rotateLeft(x.parent); else rotateRight(x.parent);
42        } else if (w.left.color == BLACK && w.right.color == BLACK) {  // case 2: push the extra black up
43            w.color = RED;
44            x = x.parent;
45        } else {
46            // cases 3 and 4: a red nephew lets rotations fix the black height
47        }
48    }
49    x.color = BLACK;
50}

Live state

0 rotations0 recolorings

black height

0

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1black height=0A red-black tree is a BST whose nodes are red or black, with these rules: the root is black, a red node has no red child, and every path from a node down to an empty child has the same number of black nodes. Insertion adds a red leaf and repairs the red-red violations; deletion repairs a missing black.
2L32black height=0 inserted=10Insert 10 as a red leaf (the root). Red keeps the black height unchanged; the only possible violation is a red parent.
3L33black height=1The root must be black: recolor 10 black.
4L32black height=1 inserted=20Insert 20 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
5L32black height=1 inserted=30Insert 30 as a red leaf, below 20. Red keeps the black height unchanged; the only possible violation is a red parent.
6L25black height=1 case=3The uncle is black and the nodes form a straight line (case 3): color the parent 20 black and the grandparent 10 red, then rotate 10 left.
7L26black height=1 case=3Rotated: 20 is now the root of this subtree, with the red children 10 and 30. The fix-up is finished.
8L32black height=1 inserted=15Insert 15 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
9L21black height=1 case=1Parent 10 and uncle 30 are both red (case 1): recolor them black and the grandparent 20 red, then continue from 20.
10L22black height=1 case=1Recolored. 20 is now red; check whether its own parent is red.
11L33black height=2The root must be black: recolor 20 black.
12L32black height=2 inserted=25Insert 25 as a red leaf, below 30. Red keeps the black height unchanged; the only possible violation is a red parent.
13L32black height=2 inserted=5Insert 5 as a red leaf, below 10. Red keeps the black height unchanged; the only possible violation is a red parent.
14L32black height=2 inserted=1Insert 1 as a red leaf, below 5. Red keeps the black height unchanged; the only possible violation is a red parent.
15L21black height=2 case=1Parent 5 and uncle 15 are both red (case 1): recolor them black and the grandparent 10 red, then continue from 10.
16L22black height=2 case=1Recolored. 10 is now red; check whether its own parent is red.
17L33keys=7 height=3 black height=27 keys, height 3, black height 2. 1 rotation and 10 recolorings in total. The longest path can be at most twice the shortest, so the height stays O(log n).
26.02.6

Properties

Collecting the guarantees: search, insert and delete all take O(log n) worst case; the height is at most 2 log2(n + 1); an insertion makes at most 2 rotations and a deletion at most 3, with only O(1) amortised recolorings per update, which is much less restructuring than AVL deletion can do. In exchange the tree may be slightly taller than an AVL tree, so lookups can be slightly slower.

Compared with AVL trees: AVL is more strictly balanced (height at most 1.44 log2 n against 2 log2 n), so it is better for lookup-heavy workloads; red-black trees update faster, which suits write-heavy workloads and general-purpose libraries. In the animation, the sorted-input preset needs 3 rotations for 7 keys, and the bend preset (10, 30, 20) 2 rotations for 3 keys.

AVL treeRed-black tree
Height bound1.44 log2(n + 2)2 log2(n + 1)
Rotations per insertionat most 2 (one rebalancing step)at most 2
Rotations per deletionup to O(log n)at most 3
Stored per nodeheight or balance factorone colour bit
26.02.7

TreeMap internals

Java's TreeMap (and TreeSet, which wraps one) is a red-black tree, a direct implementation of the algorithms above. Its entry class has a color flag along with key, value, left, right and parent, which the code below lists by reflection. HashMap also converts long collision chains into red-black trees (the TreeNode class) once a bucket gets large.

That is why TreeMap operations cost O(log n) even for sorted input, why iteration is in key order, and why firstKey, floorKey and subMap cost O(log n): they are walks on this tree. The internals are not accessible through the public API, but the fields can be inspected.

Java
1static void inspectTreeMap() throws Exception {
2    Class<?> entry = Class.forName("java.util.TreeMap$Entry");
3    List<String> fields = new ArrayList<>();
4    for (java.lang.reflect.Field f : entry.getDeclaredFields()) fields.add(f.getName());
5    Collections.sort(fields);
6    System.out.println(fields);                  // [color, key, left, parent, right, value]
7}

Practice ladder

Now try it yourself

Easy

  • Design a TreeMap-based Calendar (concept)
  • Kth Largest Element in a Stream

Medium

  • My Calendar II
  • Count of Range Sum

Advanced

  • Implement a red-black tree
  • Sliding Window Median

Key takeaways

  • Red-black rules: black root, no red node with a red child, equal black counts on every downward path.
  • Insertion colours the new node red and repairs with recolouring (case 1) or one or two rotations (cases 2 and 3).
  • Deletion repairs a missing black with four cases and at most 3 rotations.
  • Height is at most 2 log2(n + 1); updates restructure less than AVL, lookups can be slightly slower.
  • TreeMap and TreeSet are red-black trees.