Red-Black Insert Fix-up
Red uncle: recolour and move up; black uncle: one or two rotations plus a recolour, then stop.
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.
What you will see
Uncle colour decides: recolour and climb, or rotate and stop.
Cost
| Best | O(1) |
|---|---|
| Average | O(log n) |
| Worst | O(log n) |
| Space | O(1) |
At most two rotations per insert.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, left child and right child; each step announces the comparison and the direction taken or the structural change.
Reduced motion: Focus jumps node to node with a static ring; rotations become a crossfade between the two layouts.
Taught by the same lesson
Red-Black Tree covers these too, in the same run.