Tree balancing demo

Red-Black Tree

Insert and delete unique integers, then replay how recoloring and rotations restore the five red-black invariants. Red nodes, black nodes, active pivots, and violation fixes are all shown frame by frame.

Back to index Visualization notes

Controls

Insert / delete
Animation speed 700 ms

Tree stats

Black height 0
Nodes
0
Height
0
Rotations
0
Current frame
0 / 0
Ready. Try the insert demo to trigger recolors and rotations.

RB properties

5 invariants

Structure view

No operation
Yellow ring marks active nodes. Cyan rings show searched nodes. The NIL leaves are implicit but included in the property checks.
Red node
Black node
Rotation / fix focus
Search path
No frames recorded yet. Idle
    What to watch: insert fix-up either recolors an uncle-parent-grandparent trio or rotates around the parent/grandparent. Delete fix-up pushes an extra black upward until it can be absorbed by a red sibling, a rotation, or a recolor sequence.
    Complexity: search, insert, and delete are all O(log n) when the invariants hold. The color bit lets the tree stay balanced with fewer rigid constraints than AVL trees, so updates use a small number of rotations plus recoloring.

    Step explainer

    Ready

    Each frame explains what the current recolor, rotation, splice, or search comparison is doing.

    1. Build or modify the BST shape.
    2. Repair any red-red or black-height violations.
    3. Replay the frames to inspect the balancing decisions.