Red-Black Tree, step by step.

A red-black tree is a self-balancing binary search tree whose nodes are red or black: five rules on the colors keep its longest path from the root at most twice its shortest, so its height stays O(log n). After an insertion, recoloring and at most two rotations restore the rules. This page explains how it works, with step-by-step animations of the insertion cases from the VisiGrab app.

How a red-black tree works

What is a red-black tree?

A red-black tree is a binary search tree in which every node is either red or black. Five rules on these colors keep the longest path from the root at most twice the shortest, so search, insertion and deletion take O(log n) time. Rebalancing with recoloring and rotations restores the rules after an insertion or deletion.

Red-black tree properties: the five rules

  1. Node color: every node is red or black.
  2. Root property: the root is black.
  3. Leaf property: every NIL leaf is black.
  4. Red node property: a red node has no red child.
  5. Black height property (also called the depth property): from any node, every path down to a NIL leaf passes the same number of black nodes.

Below is a red-black tree of seven keys, drawn as trees usually are. The root 38 is black, the red node 20 has black children, and the red nodes 41 and 76 have no children.

A red-black tree of seven keys, NIL leaves not drawn. The black root 38 has the red child 20 and the black child 43. 20 has the black children 1 and 27; 43 has the red children 41 and 76.
A red-black tree of seven keys, drawn without its NIL leaves.

Red-black tree NIL leaves and black height

The rules speak of NIL leaves, which most drawings leave out. A NIL leaf stands for a missing child: it holds no key and counts as black. Drawn in full, the same tree has eight of them, two under each of 1, 27, 41 and 76.

The black height of a node counts the black nodes on a path from it down to a NIL leaf, without the node itself and with the NIL leaf. In the figure below, every path from the root 38 meets two black nodes: node 1 or 27 and a NIL leaf on the left, 43 and a NIL leaf on the right. Sources that also count a black start node get one more; sources that leave NIL leaves out get one less. Black depth, counted from the root down to a node, is a different measure.

The same red-black tree with its NIL leaves drawn. The black root 38 has the red child 20 and the black child 43. 20 has the black children 1 and 27; 43 has the red children 41 and 76. Each of these four nodes has two black NIL leaves.
The same tree with its NIL leaves.

Why NIL leaves? With them, every path from a node ends at a leaf of the same kind, so the black height property counts to the same end on every path. They also give a missing child a color: in insertion cases 2 and 3 below, the uncle is missing, and as a NIL leaf it counts as black. In code, one shared black sentinel node usually stands in for all NIL leaves, so the fix-up reads the color of a missing uncle like any other.

The leaf property concerns only NIL leaves; a key node with NIL children may be red, like 41 and 76.

Red-black tree height: why it stays O(log n)

With equal black counts and no two adjacent reds, the shortest possible path is all black and the longest alternates black and red, so it is at most twice as long. In the example below, step 1 shows the shortest path from the root 31 and step 2 the longest: both hold three black nodes, but one has three nodes and the other six.

Shortest and longest path

All steps as text
  1. The shortest path from the root, 31 → 17 → 8, has 3 nodes, all of them black.
  2. The longest path, 31 → 74 → 89 → 94 → 98 → 99, has 6 nodes, black and red in turn: twice as many nodes, and the same 3 black ones.
Red-Black Tree — Shortest and longest path. Last step: The longest path, 31 → 74 → 89 → 94 → 98 → 99, has 6 nodes, black and red in turn: twice the 3 of the shortest path, 31 → 17 → 8, with the same 3 black nodes.

For n keys, the height in key nodes is at most 2 log2(n + 1): at least half of the nodes on any path below the root, NIL leaf included, are black, and a subtree of black height b holds at least 2b − 1 keys.

Red-black tree insertion: why the new node is red

The new key goes down as in a binary search tree and becomes a red leaf; a key already in the tree is refused. A black node would add a black to every path through it. A red one changes no black count, so it can only break the red node property, under a red parent. With a black parent, insertion is done. The first key of an empty tree is a red root, which breaks the root property, and is recolored black.

A red parent starts the fix-up, which marks four nodes: C, the current node, first the new one; P, its parent; G, the grandparent; and U, the uncle, P's sibling. A missing uncle is a black NIL leaf, drawn as a NIL box marked U.

Red-black tree insertion cases

The fix depends on the uncle's color and on where C and P sit: on opposite sides relative to G when one is a left child and the other a right child (a triangle), on the same side when both are left or both are right children (a line).

CaseUncleC and P relative to GFix
1redeitherrecolor P and U black, G red; move C up to G
2blackopposite sidesrotate P; case 3 follows
3blacksame sideswap the colors of P and G; rotate G

A mirror image counts as the same case. This page numbers the cases as the animations and Cormen et al.'s Introduction to Algorithms do. Wikipedia numbers them I2, I5 and I6 and calls C an inner or outer grandchild; some tutorials say zig-zag and zig-zig.

Case 1: red uncle, recolor and move up

Recoloring P and U black and G red keeps every black count, but G may now have a red parent, so G becomes C and the check repeats higher up. No other case moves up.

In the player, 79 is inserted under the red 80, whose sibling 90 is red too. Case 1 runs twice, at 87 and then at the root 77, and the black height grows from 2 to 3.

Case 1: Insert node 79

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the red-black tree, it is initially colored red and becomes either the left or right child of an existing node, based on key comparisons within the tree.
  3. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  4. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  5. In this case, the current node's uncle U is red.
  6. The parent P and uncle U nodes are recolored to black, and the grandparent G to red.
  7. Move up to the grandparent, now the new current node, and repeat the rebalancing process if its parent is red.
  8. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  9. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  10. In this case, the current node's uncle U is red.
  11. The parent P and uncle U nodes are recolored to black, and the grandparent G to red.
  12. Move up to the grandparent, now the new current node, and repeat the rebalancing process if its parent is red.
  13. In the final rebalancing step, check the root's color. If it is red, recolor it to black to maintain red-black tree properties.
  14. As can be seen now, the tree is balanced and all its red-black properties are fulfilled.
Red-Black Tree — Case 1: Insert node 79. Last step: 79 is a red leaf under the black 80; 87 above them is red, the root 77 is black, and no red node has a red child.

Case 2: black uncle, opposite sides, rotate the parent

P is rotated down, away from C, which takes its place. The old parent becomes C; now C and P are on the same side, so case 3 follows at once.

In the player, 25 is inserted as the right child of the red 24, the left child of 28, whose right child is NIL. A left rotation on 24 lifts 25, case 3 follows, and 25 ends black, with the red children 24 and 28.

Case 2: Insert node 25

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the red-black tree, it is initially colored red and becomes either the left or right child of an existing node, based on key comparisons within the tree.
  3. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  4. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  5. In this configuration, the uncle node U is black, and the current node C and its parent P are positioned on opposite sides relative to the grandparent G.
  6. The markers are reassigned to reflect the new roles: the parent is now marked as C, becoming the new current node.
  7. An arrow is now displayed above the node around which the rotation will occur.
  8. The node with key 24 is rotated downwards and to the left.
  9. After the rotation, the links are reconfigured: the node marked P becomes a child of the node marked G. Despite this, the tree remains imbalanced, necessitating additional adjustments.
  10. In this scenario, the uncle node U is black, and both the current node C and its parent P are located on the same side in relation to the grandparent G.
  11. The colors are swapped: the parent P becomes black, and the grandparent G turns red.
  12. An arrow is now displayed above the node around which the rotation will occur.
  13. The node with key 28 is rotated downwards and to the right.
  14. Update the tree structure: set the node with key 25 as the right child of the node with key 19.
  15. As can be seen now, the tree is balanced and all its red-black properties are fulfilled.
Red-Black Tree — Case 2: Insert node 25. Last step: 19 is the black root over the black 14 and 25, which have the red children 1, 16, 24 and 28.

Case 3: black uncle, same side, rotate the grandparent

P and G swap colors, and G is rotated down, away from C. P takes G's place, black with two red children, and the fix-up ends.

In the same tree as in case 2, 20 goes in as the left child of 24, on the same side as 24 under 28, so a single right rotation on 28 is enough: 24 ends black, with the red children 20 and 28.

Case 3: Insert node 20

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the red-black tree, it is initially colored red and becomes either the left or right child of an existing node, based on key comparisons within the tree.
  3. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  4. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  5. In this scenario, the uncle node U is black, and both the current node C and its parent P are located on the same side in relation to the grandparent G.
  6. The colors are swapped: the parent P becomes black, and the grandparent G turns red.
  7. An arrow is now displayed above the node around which the rotation will occur.
  8. The node with key 28 is rotated downwards and to the right.
  9. Update the tree structure: set the node with key 24 as the right child of the node with key 19.
  10. As can be seen now, the tree is balanced and all its red-black properties are fulfilled.
Red-Black Tree — Case 3: Insert node 20. Last step: 19 is the black root over the black 14 and 24, which have the red children 1, 16, 20 and 28.

Red-black tree case 1-2-3: when cases chain

Case 1 can leave a red G under a red parent, so another case can follow.

In the player, 66 is inserted under the red 64, whose sibling 82 is red: case 1 recolors and moves up to 78, whose uncle 21 is a black key node, not a NIL leaf. Cases 2 and 3 follow, and 78 becomes the root, with the red children 58 and 84.

Case 1-2-3: Insert node 66

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the red-black tree, it is initially colored red and becomes either the left or right child of an existing node, based on key comparisons within the tree.
  3. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  4. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  5. In this case, the current node's uncle U is red.
  6. The parent P and uncle U nodes are recolored to black, and the grandparent G to red.
  7. Move up to the grandparent, now the new current node, and repeat the rebalancing process if its parent is red.
  8. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  9. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  10. In this configuration, the uncle node U is black, and the current node C and its parent P are positioned on opposite sides relative to the grandparent G.
  11. The markers are reassigned to reflect the new roles: the parent is now marked as C, becoming the new current node.
  12. An arrow is now displayed above the node around which the rotation will occur.
  13. The node with key 84 is rotated downwards and to the right.
  14. After the rotation, the links are reconfigured: the node marked P becomes a child of the node marked G. Despite this, the tree remains imbalanced, necessitating additional adjustments.
  15. In this scenario, the uncle node U is black, and both the current node C and its parent P are located on the same side in relation to the grandparent G.
  16. The colors are swapped: the parent P becomes black, and the grandparent G turns red.
  17. An arrow is now displayed above the node around which the rotation will occur.
  18. The node with key 58 is rotated downwards and to the left. The node with key 78 becomes the new root.
  19. As can be seen now, the tree is balanced and all its red-black properties are fulfilled.
Red-Black Tree — Case 1-2-3: Insert node 66. Last step: 78 is the black root over the red 58 and 84; below them are the black 21, 64, 82 and 85, and 66 is a red leaf under 64.

Why is a red-black tree always balanced?

Two of its rules keep it roughly balanced: a red node has no red child, and every path from a node down to a NIL leaf passes the same number of black nodes. The shortest possible path is then all black and the longest alternates black and red, so it is at most twice as long, and the height stays at most 2 log2(n + 1). The first player shows the shortest and the longest path of one tree.

Red-black tree rotations: at most two per insertion

Case 3 alone is a single rotation, like the AVL LL and RR rotations; case 2 then case 3 is a double rotation, like LR and RL. Case 3 always ends the fix-up, so an insertion needs at most two rotations. Case 1 only recolors, but it can climb O(log n) levels.

Red-black tree deletion

Deletion starts as in a binary search tree: a node with two children is replaced by its in-order successor, which takes its color, so the node that really leaves its position is the successor. A red one breaks nothing. A black one leaves its paths one black short: a red child that moves up is recolored black, otherwise the empty NIL leaf is marked double black. Four cases, set by the sibling's color and its children, absorb the extra black or pass it up, with at most three rotations.

Red-black tree time complexity

MeasureWorst case
SearchO(log n)
InsertO(log n), at most 2 rotations
DeleteO(log n), at most 3 rotations
Heightat most 2 log2(n + 1)
SpaceO(n)

AVL tree vs red-black tree: which is faster?

For lookups, usually the AVL tree, whose stricter balance keeps it lower; for deletions, usually the red-black tree, which rotates less. The next section gives their heights and rotation counts.

Red-black tree vs AVL tree

Both are approximately balanced, by different rules. An AVL tree limits the height difference at every node to one, which keeps its height below about 1.44 log2 n; a red-black tree limits the longest path to twice the shortest, about 2 log2 n. On deletion, a red-black tree rotates at most three times, an AVL tree possibly at every level up to the root. The stricter AVL rule gives shorter lookups.

Red-black trees and 2-3-4 trees

A black node and its red children act as one node with up to three keys. Read this way, a red-black tree is a 2-3-4 tree, a B-tree of maximum degree 4, and case 1 corresponds to a node split.

Where red-black trees are used

  • Java: TreeMap and TreeSet; since Java 8, HashMap also turns a bucket of more than eight entries into a red-black tree once the table has at least 64 buckets.
  • C++: std::map and std::set in libstdc++, libc++ and Microsoft's library, though the standard does not require it.
  • Linux: the kernel's rbtree library, used by the scheduler and by epoll.

The full source code is on GitHub, in Python, Java and C++.

Four insertions here.
The whole topic in the app.

In VisiGrab you build the tree yourself, and every change plays out step by step.

Your own tree

Insert any key with “+”, tap a node to delete it, or start from a random tree. Every insert and delete is kept in a list.

Forward and back

Step through every recoloring and rotation, and step back through them. Show or hide the NIL leaves and the C, P, G, U markers.

Deletion too

The double black and its four cases, each with an example to step through.

Theory with examples

The five rules, NIL leaves, black height and every insertion and deletion case, with interactive examples.

Python, Java and C++

A complete red-black tree implementation, explained part by part.

Quiz

Check what you have learned before moving on.

Fix a red-black tree
case by case.

Download VisiGrab and step through every insertion, deletion and case yourself.

The red-black tree is one of 30+ topics. See them all