AVL Tree Rotations
Visualize self-balancing binary search trees through balance factors and rotations.
Free theory articleVisualize self-balancing binary search trees through balance factors and rotations.
Concept & interpretation
An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree in which the balance factor BF(N) = Height(N.left) − Height(N.right) of every node N is restricted to {−1, 0, 1}. Whenever an insertion or deletion causes |BF(N)| = 2, one of four local pointer rotations (LL, RR, LR, or RL) restores the height invariant in O(1) structural work, guaranteeing worst-case O(log n) search, insertion, and deletion time.
Interactive Experiment: What to Enter and Observe
Open the AVL Tree Rotations module to watch balance factors update and trigger single or double rotations:
- Set Nodes to Insert to
10and Animation Speed to1200msso each insertion step is easy to inspect. - Inspect the Pending Insertions queue in the bottom-left panel, then click Play.
- Watch the
bf=...badge below each node on the canvas and the Status message: whenever an insertion pushes an ancestor to |bf| = 2, the Status card reports the exact rebalancing operation (Right Rotate,Left Rotate,Left-Right Rotate, orRight-Left Rotate) and the subtree height drops by 1. - Click Pause right after a rotation to verify that every node on the canvas again satisfies
bf ∈ {-1, 0, 1}, or increase Nodes to Insert to30to confirm the total tree depth never exceeds 5 levels.