In a standard binary search tree (BST), lookup speed depends entirely on the order in which keys are inserted. If keys arrive in sorted or nearly sorted order, a standard BST degenerates into a linked list: tree height grows to O(n), and search degrades from logarithmic to linear time.
The AVL tree, introduced in 1962 by Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis, solves this by maintaining a strict local balance condition after every insertion and deletion. Whenever an operation causes a subtree to become too tall on one side, the tree applies a rotation to restore balance while preserving the binary search tree ordering.
In US data structures courses, such as CS 61B or Introduction to Algorithms, AVL tree rotations are a classic midterm and exam topic. This guide walks through the balance factor rules, all four rotation cases (LL, RR, LR, and RL), a complete 9-key insertion sequence with values computed by ToolSphere's data structure library, and a side-by-side comparison with an unbalanced BST.
Balance Factor and the AVL Invariant
Every node in an AVL tree tracks or derives its height and its balance factor:
- Height convention: The height of a node is the number of edges on the longest downward path from that node to a leaf. A leaf node has height 0, a node with a single leaf child has height 1, and an empty (null) link has height -1:
Height(node) = 1 + max(Height(left), Height(right)) - Balance factor formula: The balance factor (BF) measures the height difference between the left and right subtrees:
Balance Factor = Height(left) − Height(right) - The AVL invariant: A binary search tree is an AVL tree if and only if every node satisfies:
Balance Factor ∈ {-1, 0, +1}
When an inserted node causes any ancestor to reach a balance factor of +2 (left-heavy) or -2 (right-heavy), the subtree rooted at the lowest unbalanced ancestor must be rebalanced immediately using one of four rotation types.
The Four Rotation Cases
The rotation required depends on the shape of the insertion path below the unbalanced node. We name each case with two letters:
- First letter: The heavy child of the unbalanced node (Left or Right).
- Second letter: The direction of the grandchild where the key was inserted (Left or Right).
1. LL Case: Single Right Rotation
An LL (Left-Left) imbalance occurs when a key is inserted into the left subtree of the left child of an ancestor node A. Node A ends up with a balance factor of +2, and its left child B has a balance factor of +1.
A (+2) B (0)
/ \ / \
B (+1) T3 === Rotate ==> 10 (0) A (0)
/ \ Right at A / \
10 (0) T2 T2 T3
Pointer updates:
- Node
Bis promoted to takeA's place as the subtree root. B's right subtree (T2) becomes the left subtree ofA.- Node
Abecomes the right child ofB.
Canonical minimal example: Insert 30, then 20, then 10.
- Inserting 30 creates the root (h = 0, BF = 0).
- Inserting 20 makes 20 the left child of 30 (30 has h = 1, BF = +1).
- Inserting 10 makes 10 the left child of 20. Node 30 now has left height 1 and right height -1:
BF(30) = 1 - (-1) = +2. Its left child 20 hasBF(20) = 0 - (-1) = +1. - Applying a right rotation at 30 promotes 20 to the root:
- Root: 20 (height = 1, BF = 0)
- Left child: 10 (height = 0, BF = 0)
- Right child: 30 (height = 0, BF = 0)
2. RR Case: Single Left Rotation
An RR (Right-Right) imbalance is the exact mirror of the LL case. It occurs when a key is inserted into the right subtree of the right child of an ancestor node A. Node A has a balance factor of -2, and its right child B has a balance factor of -1.
A (-2) B (0)
/ \ / \
T1 B (-1) === Rotate ==> A (0) 30 (0)
/ \ Left at A / \
T2 30 (0) T1 T2
Pointer updates:
- Node
Bis promoted to takeA's place as the subtree root. B's left subtree (T2) becomes the right subtree ofA.- Node
Abecomes the left child ofB.
Canonical minimal example: Insert 10, then 20, then 30.
- Inserting 10 creates the root (h = 0, BF = 0).
- Inserting 20 makes 20 the right child of 10 (10 has h = 1, BF = -1).
- Inserting 30 makes 30 the right child of 20. Node 10 now has left height -1 and right height 1:
BF(10) = -1 - 1 = -2. Its right child 20 hasBF(20) = -1 - 0 = -1. - Applying a left rotation at 10 promotes 20 to the root:
- Root: 20 (height = 1, BF = 0)
- Left child: 10 (height = 0, BF = 0)
- Right child: 30 (height = 0, BF = 0)
3. LR Case: Double Left-Right Rotation
An LR (Left-Right) imbalance occurs when a key is inserted into the right subtree of the left child of an ancestor node A. Node A has a balance factor of +2, but its left child B has a balance factor of -1. This produces a "zigzag" or bent path: left, then right.
A single right rotation at A cannot balance this tree because the excess height is on the inside right branch of B. Instead, the tree applies a double rotation:
- Left rotation at child B: Promotes grandchild
Cto become the new left child ofA, withBasC's left child. This transforms the bent LR shape into a straight LL shape. - Right rotation at ancestor A: Promotes
Cto become the subtree root, placingBon its left andAon its right.
A (+2) A (+2) C (0)
/ \ / \ / \
B (-1) T4 == Step 1 ==>C T4 == Step 2 ==>B (0) A (0)
/ \ Left at B / \ Right at A / \ / \
T1 C B T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
Canonical minimal example: Insert 30, then 10, then 20.
- Inserting 30 creates root 30.
- Inserting 10 makes 10 the left child of 30.
- Inserting 20 makes 20 the right child of 10. Node 30 has left height 1 and right height -1 (
BF = +2). Left child 10 has left height -1 and right height 0 (BF = -1). - Step 1: Rotate left at 10. Node 20 becomes the left child of 30; 10 becomes 20's left child. The path from 30 is now 30 -> 20 -> 10 (an LL shape).
- Step 2: Rotate right at 30. Node 20 becomes the root, with left child 10 and right child 30:
- Root: 20 (height = 1, BF = 0)
- Left child: 10 (height = 0, BF = 0)
- Right child: 30 (height = 0, BF = 0)
4. RL Case: Double Right-Left Rotation
An RL (Right-Left) imbalance is the mirror of the LR case. It occurs when a key is inserted into the left subtree of the right child of an ancestor node A. Node A has a balance factor of -2, and its right child B has a balance factor of +1 (a bent path: right, then left).
- Right rotation at child B: Straightens the path into an RR shape by promoting grandchild
Cto become the right child ofA. - Left rotation at ancestor A: Promotes
Cto become the subtree root, placingAon its left andBon its right.
Canonical minimal example: Insert 10, then 30, then 20.
- Inserting 10 creates root 10.
- Inserting 30 makes 30 the right child of 10.
- Inserting 20 makes 20 the left child of 30. Node 10 has left height -1 and right height 1 (
BF = -2). Right child 30 has left height 0 and right height -1 (BF = +1). - Step 1: Rotate right at 30. Node 20 becomes the right child of 10, with 30 as 20's right child (straightened RR shape).
- Step 2: Rotate left at 10. Node 20 becomes the root, with left child 10 and right child 30:
- Root: 20 (height = 1, BF = 0)
- Left child: 10 (height = 0, BF = 0)
- Right child: 30 (height = 0, BF = 0)
Worked Example: 9-Key Insertion Sequence
To see all four rotation cases in an actual working tree, we trace the insertion sequence:
[30, 20, 10, 25, 28, 40, 50, 60, 55]
This sequence builds directly on the 7-key example loaded by default in ToolSphere's Data Structure Visualizer, extending it with keys 60 and 55 so that every single rotation type (LL, LR, RR, and RL) appears in order. All heights and balance factors below are computed directly by running src/lib/ds/structures.ts.
Step 1: Insert 30
- Tree state: Single node 30.
- Height = 0, Balance Factor = 0.
Step 2: Insert 20
- Key 20 < 30: inserted as left child of 30.
- Node 20: height = 0, BF = 0.
- Node 30: height = 1, BF = 1 - (-1) = +1. Tree remains balanced.
Step 3: Insert 10 (Triggers LL Rotation)
- Key 10 < 30 (go left), 10 < 20 (go left): inserted as left child of 20.
- Node 10: height = 0, BF = 0.
- Node 20: height = 1, BF = 0 - (-1) = +1.
- Node 30: left height = 1, right height = -1.
BF(30) = 1 - (-1) = +2(Imbalance!). - Because child 20 has
BF = +1, this is an LL case at 30. - Action: Single right rotation at 30.
- Result: Node 20 becomes root; 10 is left child; 30 is right child.
- In-order:
[10, 20, 30], Level-order:[20, 10, 30]. - Tree height: 1. All balance factors: 0.
- In-order:
Step 4: Insert 25
- Key 25 > 20 (go right), 25 < 30 (go left): inserted as left child of 30.
- Node 25: height = 0, BF = 0.
- Node 30: height = 1, BF = 0 - (-1) = +1.
- Root 20: left height = 0 (node 10), right height = 1 (node 30).
BF(20) = 0 - 1 = -1. - Tree height: 2. All nodes satisfy
|BF| <= 1.
Step 5: Insert 28 (Triggers LR Rotation)
- Key 28 > 20 (go right), 28 < 30 (go left), 28 > 25 (go right): inserted as right child of 25.
- Let us check ancestors walking up from 28:
- Node 25: left height = -1, right height = 0 -> height = 1,
BF(25) = -1 - 0 = -1. - Node 30: left height = 1 (subtree at 25), right height = -1 -> height = 2,
BF(30) = 1 - (-1) = +2(Imbalance!). - Because child 25 has
BF = -1, this is an LR case at 30.
- Node 25: left height = -1, right height = 0 -> height = 1,
- Action: Double rotation: rotate left at 25, then right at 30.
- Rotate left at 25: Node 28 replaces 25 as left child of 30, with 25 becoming 28's left child.
- Rotate right at 30: Node 28 takes 30's position as right child of 20, with 25 on its left and 30 on its right.
- Result:
- Root: 20 (height = 2, BF = -1)
- Left child of 20: 10 (height = 0, BF = 0)
- Right child of 20: 28 (height = 1, BF = 0), with left child 25 (h = 0) and right child 30 (h = 0).
- In-order:
[10, 20, 25, 28, 30], Level-order:[20, 10, 28, 25, 30].
Step 6: Insert 40 (Triggers RR Rotation at Root)
- Key 40 > 20 (go right), 40 > 28 (go right), 40 > 30 (go right): inserted as right child of 30.
- Ancestors:
- Node 30: left height = -1, right height = 0 -> height = 1,
BF(30) = -1 - 0 = -1. - Node 28: left height = 0 (node 25), right height = 1 (node 30) -> height = 2,
BF(28) = 0 - 1 = -1. - Root 20: left height = 0 (node 10), right height = 2 (subtree at 28) ->
BF(20) = 0 - 2 = -2(Imbalance!). - Because right child 28 has
BF = -1, this is an RR case at root 20.
- Node 30: left height = -1, right height = 0 -> height = 1,
- Action: Single left rotation at 20.
- Result: Node 28 becomes the new root of the entire tree!
- Node 20 becomes left child of 28, adopting 25 as its right child.
- Node 30 remains right child of 28, with right child 40.
- Root: 28 (height = 2, BF = 0)
- Left branch: 20 (h = 1, BF = 0), with left 10 and right 25.
- Right branch: 30 (h = 1, BF = -1), with right 40.
- In-order:
[10, 20, 25, 28, 30, 40], Level-order:[28, 20, 30, 10, 25, 40].
Step 7: Insert 50 (Triggers RR Rotation in Subtree)
- Key 50 > 28 (go right), 50 > 30 (go right), 50 > 40 (go right): inserted as right child of 40.
- Ancestors:
- Node 40: left height = -1, right height = 0 -> height = 1,
BF(40) = -1. - Node 30: left height = -1, right height = 1 (subtree at 40) ->
BF(30) = -1 - 1 = -2(Imbalance!). - Because right child 40 has
BF = -1, this is an RR case at 30.
- Node 40: left height = -1, right height = 0 -> height = 1,
- Action: Single left rotation at 30.
- Result: Node 40 becomes right child of root 28, with left child 30 and right child 50.
- Root: 28 (height = 2, BF = 0)
- Left child: 20 (h = 1, BF = 0), with children 10 and 25.
- Right child: 40 (h = 1, BF = 0), with children 30 and 50.
- Every one of the 7 nodes has
BF = 0! The tree is a complete, perfectly balanced binary tree. - Level-order:
[28, 20, 40, 10, 25, 30, 50].
Step 8: Insert 60
- Key 60 > 28, 60 > 40, 60 > 50: inserted as right child of 50.
- Node 50: height = 1, BF = -1.
- Node 40: left height = 0 (node 30), right height = 1 (node 50) -> height = 2,
BF(40) = 0 - 1 = -1. - Root 28: left height = 1 (node 20), right height = 2 (node 40) -> height = 3,
BF(28) = 1 - 2 = -1. - All nodes satisfy
|BF| <= 1; no rotation needed.
Step 9: Insert 55 (Triggers RL Rotation)
- Key 55 > 28, 55 > 40, 55 > 50, 55 < 60: inserted as left child of 60.
- Ancestors:
- Node 60: left height = 0 (node 55), right height = -1 -> height = 1,
BF(60) = 0 - (-1) = +1. - Node 50: left height = -1, right height = 1 (subtree at 60) ->
BF(50) = -1 - 1 = -2(Imbalance!). - Because right child 60 has
BF = +1, this is an RL case at 50.
- Node 60: left height = 0 (node 55), right height = -1 -> height = 1,
- Action: Double rotation: rotate right at 60, then left at 50.
- Rotate right at 60: Node 55 becomes the right child of 50, with 60 as 55's right child.
- Rotate left at 50: Node 55 replaces 50 as right child of 40, with 50 as its left child and 60 as its right child.
- Final AVL Tree Structure:
- Root: 28 (height = 3, BF = -1)
- Left subtree of 28: node 20 (h = 1, BF = 0), with left 10 (h = 0) and right 25 (h = 0).
- Right subtree of 28: node 40 (h = 2, BF = -1), with left 30 (h = 0) and right 55 (h = 1, BF = 0).
- Children of 55: left 50 (h = 0, BF = 0) and right 60 (h = 0, BF = 0).
- In-order traversal:
[10, 20, 25, 28, 30, 40, 50, 55, 60] - Level-order traversal:
[28, 20, 40, 10, 25, 30, 55, 50, 60]
Comparing the AVL Tree with an Unbalanced BST
What happens if we insert those exact same 9 keys in the exact same order into an ordinary binary search tree without balancing?
Final BST Structure (No Rotations)
Without rotations, nodes remain where they were originally attached:
30 (h=4, BF=-1)
/ \
20 (h=2, BF=-1) 40 (h=3, BF=-3) <-- Severely unbalanced!
/ \ \
10 (0) 25 (h=1, BF=-1) 50 (h=2, BF=-2)
\ \
28 (0) 60 (h=1, BF=+1)
/
55 (0)
Look at the right subtree of the BST:
- Node 40 has left height -1 and right height 2 ->
BF(40) = -3. - Node 50 has left height -1 and right height 1 ->
BF(50) = -2. - The tree height is 4 (5 levels of nodes), and the longest path runs
30 -> 40 -> 50 -> 60 -> 55.
Node-by-Node Metric Comparison
| Metric | AVL Tree | Unbalanced BST | Difference |
|---|---|---|---|
| Root key | 28 | 30 | AVL promotes median keys |
| Tree height (edges) | 3 | 4 | AVL is 25% shallower |
| Worst-case search depth | 3 comparisons | 5 comparisons | 40% fewer checks for key 55 |
| Search path for 55 | 28 -> 40 -> 55 (3 nodes) | 30 -> 40 -> 50 -> 60 -> 55 (5 nodes) | 2 fewer comparisons |
| Search path for 28 | 28 (root, 1 check) | 30 -> 20 -> 25 -> 28 (4 checks) | 75% faster lookup |
| Max balance factor | -1 (within [-1, 1]) |
-3 (violates invariant) | AVL maintains balance |
The Worst-Case Scenario: Sorted Insertion
The difference becomes even more extreme when keys arrive in sorted order [10, 20, 25, 28, 30, 40, 50]:
- Unbalanced BST: Degenerates into a single straight line:
10 -> 20 -> 25 -> 28 -> 30 -> 40 -> 50. Height is 6, and searching for 50 requires examining all 7 nodes—linear O(n) performance. - AVL Tree: Continually performs RR rotations during insertion. The final AVL tree has root 28, children 20 and 40, and leaves 10, 25, 30, 50. Height is only 2, and any key can be found in at most 3 comparisons—true O(log n) performance.
| Operation | AVL Tree (Worst Case) | Unbalanced BST (Worst Case) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Height guarantee | <= 1.44 * log2(n) | Up to n - 1 |
| Rotation overhead | At most 1 or 2 per insert; up to O(log n) on delete | None (0 rotations) |
AVL trees trade a tiny amount of rotation overhead during insertions and deletions for a strict, guaranteed upper bound on height. For read-heavy applications where lookups dominate, this guarantee is well worth the extra pointer reassignments.
Common Midterm and Exam Pitfalls
When tracing AVL trees on homework or exams, watch out for these frequent mistakes:
- Rebalancing the wrong node: Always trace from the newly inserted leaf upward to the root. The first node you encounter with
|BF| > 1is the pivot ancestor where the rotation must take place. Rebalancing any node higher up without fixing the lowest unbalanced ancestor will fail. - Confusing LL with Left Rotation: Remember that the rotation direction is opposite the heavy direction. An LL imbalance is left-heavy, so you fix it with a right rotation. An RR imbalance is right-heavy, so you fix it with a left rotation.
- Checking the grandchild vs. checking the child's balance factor: To distinguish LL from LR, look at the left child's balance factor:
- If child's BF >= 0, it is an LL case (single right rotation).
- If child's BF < 0, it is an LR case (double rotation: left at child, then right at ancestor).
- Forgetting to update heights: After a rotation, the heights of both the old root and the new root change. If you do not update their heights immediately, subsequent balance factor calculations for ancestors higher up the tree will be incorrect.
- In-order traversal check: A rotation changes tree structure, but it must never change the sorted order of keys. After drawing any rotation on paper, write down the in-order traversal (left-root-right). If the keys are not strictly in ascending order, a pointer was attached to the wrong side.
Verify Your Work with the Interactive Visualizer
To test your own insertion sequences or practice for a data structures exam, open ToolSphere's Data Structure Visualizer.
Select AVL Tree, clear the structure or load the default example, and insert keys one by one. The tool displays the exact height, node count, and sorted in-order traversal above the tree diagram, and prints an operation trace naming every comparison and rotation case (LL, RR, LR, RL) with its pivot nodes.
Use the Graph Algorithm Visualizer to explore graph algorithm steps. For a related walkthrough, read Master Theorem: 10 Solved Examples.