Red-Black Tree
A search tree kept within 2 log n height by one colour bit per node and a fixup after each insert.
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
Nodes coloured red or black (plus a shape cue); violations trigger recolouring or rotation.
Cost
| search | O(log n) |
|---|---|
| insert | O(log n) |
| delete | O(log n) |
| Space | O(n) |
Fewer rotations than AVL on insert; slightly taller trees.
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, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Red-Black Tree covers these too, in the same run.