Red-Black Tree, step by step.

// how red-black trees work

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 colours keep the longest path from the root at most twice the shortest, so search, insertion and deletion take O(log n) time. Rebalancing with recolouring and rotations restores the rules after an insertion or deletion.

Red-black tree properties: the five rules

1. Node colour: 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.

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.

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 colour: 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 colour 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.

For n keys, the height in key nodes is at most 2 log₂(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 2^b − 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 recoloured 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 colour 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).

Case	Uncle	C and P relative to G	Fix
1	red	either	recolour P and U black, G red; move C up to G
2	black	opposite sides	rotate P; case 3 follows
3	black	same side	swap the colours 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, recolour and move up

Recolouring 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.

Here 79 is inserted as the left child of the red 80. With C = 79, P = 80, U = 90 (red) and G = 87, nodes 80 and 90 turn black and 87 red. 87's parent 93 is red, so case 1 repeats with C = 87, P = 93, U = 14 (red) and G = 77: 93 and 14 turn black, the root 77 red. The red root is then recoloured black. Because 93 and 14 turned black, the black height grows from 2 to 3. Step through it below.

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.

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.

Here 25 is inserted as the right child of the red 24, the left child of 28: C = 25, P = 24, G = 28, and U is the NIL right child of 28. A left rotation on 24 lifts 25; case 3 then makes 25 black and 28 red and rotates 28 to the right. 25 ends black, with the red children 24 and 28. Step through it below.

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.

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

P and G swap colours, 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 is inserted as the left child of 24: C = 20, P = 24, G = 28, and U is again the NIL right child of 28. 24 turns black and 28 red, and a right rotation on 28 leaves 24 with the red children 20 and 28. Step through it below.

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 1-2-3: when cases chain

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

Here 66 is inserted as the right child of the red 64. With C = 66, P = 64, U = 82 (red) and G = 78, case 1 turns 64 and 82 black and 78 red. Then C = 78, P = 84 (red), G = 58, and U = 21, a black key node, not a NIL leaf. 78 is a left child and 84 a right child: case 2. A right rotation on 84 lifts 78; case 3 then makes 78 black and 58 red and rotates the root 58 to the left. 78 becomes the root, with the red children 58 and 84. Step through it below.

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 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 recolours, 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 colour, 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 recoloured black, otherwise the empty NIL leaf is marked double black. Four cases, set by the sibling's colour and its children, absorb the extra black or pass it up, with at most three rotations.

Red-black tree time complexity

Measure	Worst case
Search	O(log n)
Insert	O(log n), at most 2 rotations
Delete	O(log n), at most 3 rotations
Height	at most 2 log2(n + 1)
Space	O(n)

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 log₂ n; a red-black tree limits the longest path to twice the shortest, about 2 log₂ 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.