Insert 10, 20, 30, 40, 50, 60, 70, 80 into a red-black tree. Red nodes are outlined red, black nodes are plain. Every new node arrives red, so the only rule it can break is that a red node must have black children. The fixup repairs that with recolouring and at most two rotations per insert.
Building a red-black tree from 8 values.
Insert 10 as an ordinary BST insert, coloured red. It is the root.
Inserted 10 as a red leaf.
The root 10 ended up red, so it is coloured black: rule 2. That adds one to every path's black count equally.
Root 10 set black.
Insert 20 as an ordinary BST insert, coloured red under 10, which is black: nothing is broken.
Inserted 20 as a red leaf.
Insert 30 as an ordinary BST insert, coloured red under 20, which is red: two reds in a row, so the fixup runs.
Inserted 30 as a red leaf.
z = 30 is red under a red parent p = 20. Grandparent g = 10, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 30.
20 turns black and 10 red, then rotate left at 10: 20 takes 10's place with 10 and 30 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 10. 20 is the black top.
Insert 40 as an ordinary BST insert, coloured red under 30, which is red: two reds in a row, so the fixup runs.
Inserted 40 as a red leaf.
z = 40 is red under a red parent p = 30. Grandparent g = 20, uncle u = 10. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 40.
30 and 10 are black, 20 is red. z moves up to 20, the root, which will be set black at the end.
Recoloured. z is now 20.
The root 20 ended up red, so it is coloured black: rule 2. That adds one to every path's black count equally.
Root 20 set black.
Insert 50 as an ordinary BST insert, coloured red under 40, which is red: two reds in a row, so the fixup runs.
Inserted 50 as a red leaf.
z = 50 is red under a red parent p = 40. Grandparent g = 30, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 50.
40 turns black and 30 red, then rotate left at 30: 40 takes 30's place with 30 and 50 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 30. 40 is the black top.
Insert 60 as an ordinary BST insert, coloured red under 50, which is red: two reds in a row, so the fixup runs.
Inserted 60 as a red leaf.
z = 60 is red under a red parent p = 50. Grandparent g = 40, uncle u = 30. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 60.
50 and 30 are black, 40 is red. z moves up to 40, whose parent 20 is black: done.
Recoloured. z is now 40.
Insert 70 as an ordinary BST insert, coloured red under 60, which is red: two reds in a row, so the fixup runs.
Inserted 70 as a red leaf.
z = 70 is red under a red parent p = 60. Grandparent g = 50, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 70.
60 turns black and 50 red, then rotate left at 50: 60 takes 50's place with 50 and 70 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 50. 60 is the black top.
Insert 80 as an ordinary BST insert, coloured red under 70, which is red: two reds in a row, so the fixup runs.
Inserted 80 as a red leaf.
z = 80 is red under a red parent p = 70. Grandparent g = 60, uncle u = 50. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 80.
70 and 50 are black, 60 is red. z moves up to 60, whose parent 40 is red too: another round.
Recoloured. z is now 60.
z = 60 is red under a red parent p = 40. Grandparent g = 20, uncle u = 10. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 60.
40 turns black and 20 red, then rotate left at 20: 40 takes 20's place with 20 and 60 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 20. 40 is the black top.
8 nodes, height 4, after 4 rotations and 19 recolourings. The rules keep the longest root-to-leaf path at most twice the shortest, so the height is at most 2 log2(n + 1), about 6 here, and every operation stays O(log n).
Red-black tree with 8 nodes and height 4.