AVL Tree Rotations
Visualize self-balancing binary search trees through balance factors and rotations.
By Riano · Published · Updated · Report a correction
AVL Tree Rotations
Concept Overview
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.
Mathematical Definition
For any node N in an AVL tree of n nodes:
Worst-case height bound:
h < 1.4405 log2(n + 2) − 0.3277
Worked Example: Single (LL) vs. Double (LR) Rotation
Compare inserting the descending triple 30, 20, 10 with the zig-zag triple 30, 10, 20 into an empty AVL tree:
- LL Case (insert 30, 20, 10): After inserting 30 and 20, BF(30) = +1. Inserting 10 as the left child of 20 makes Height(20) = 2 and BF(30) = 2 − 0 = +2 with BF(20) = +1. A single Right Rotation around 30 promotes 20 to the root with left child 10 and right child 30, restoring BF = 0 at every node and reducing tree height from 3 to 2.
- LR Case (insert 30, 10, 20): Inserting 20 as the right child of left child 10 makes BF(30) = +2 while BF(10) = −1 (opposite signs). A single right rotation on 30 would merely mirror the imbalance. Instead, an LR Double Rotation first Left-Rotates child 10 (making 20 the left child of 30 with 10 on its left), then Right-Rotates 30 to place 20 at the root over 10 and 30.
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.
Assumptions & Trade-offs
While a single insertion in an AVL tree requires at most one rotation (single or double) at the lowest unbalanced ancestor, an AVL deletion can trigger O(log n) rotations cascading all the way to the root. Because AVL trees enforce a tighter height bound (1.44 log2 n) than Red-Black trees (2 log2 n), AVL trees provide faster lookups on read-heavy workloads but incur slightly higher structural update costs on write-heavy workloads.
References
Adelson-Velsky and Landis introduced the height-balanced binary search tree in 1962, and MIT 6.006 Lecture 6 derives the Fibonacci minimum-node recurrence Nh = 1 + Nh−1 + Nh−2 that yields the 1.44 log2 n height bound:
- Demaine, E., Ku, J., & Solomon, J. MIT 6.006 Introduction to Algorithms, Lecture 6: Binary Trees II (AVL Trees). MIT OpenCourseWare. MIT 6.006 Lecture 6 Notes (PDF)
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive AVL Tree Rotations module.
Try AVL Tree Rotations on Riano →