AVL Tree Rotations Explained: LL, RR, LR, RL with Examples
A complete, GATE-ready guide to all four AVL tree rotation cases — balance factor calculation, step-by-step tree diagrams, Python code, and worked GATE examples.
Last updated: April 18, 2026 | Topic: Data Structures | Level: B.Tech / GATE CS
Key Takeaways
- An AVL tree is a self-balancing BST where every node’s balance factor ∈ {−1, 0, +1}.
- There are 4 rotation cases: LL (single right), RR (single left), LR (left-right double), RL (right-left double).
- LL and RR are single rotations; LR and RL are double rotations (two single rotations combined).
- All AVL operations (search, insert, delete) run in O(log n) worst case.
- Insertion requires at most 1 rotation; deletion may require O(log n) rotations.
- AVL height is always ≤ 1.44 log₂(n+2) — strictly controlled.
- GATE frequently asks: identify rotation type, compute balance factor, draw resulting tree after rotation.
1. What Is an AVL Tree?
An AVL tree (named after Adelson-Velsky and Landis, 1962) is a Binary Search Tree (BST) that automatically keeps itself height-balanced. After every insertion or deletion, it checks whether any node has become unbalanced and fixes it by performing rotations.
The problem AVL trees solve: a plain BST can degrade to a linear chain (height = n) if keys are inserted in sorted order, making all operations O(n). AVL trees guarantee O(log n) operations by capping height at 1.44 log₂ n.
|height(N.left) − height(N.right)| ≤ 1
Height of an AVL tree with n nodes: h ≤ 1.44 log₂(n + 2) − 0.328
2. Balance Factor — Definition and Calculation
Height of null (empty) subtree = −1 (or 0 depending on convention; GATE uses height of empty = −1).
Example — compute BF for every node:
30 (BF = ?)
/ \
20 40 (BF = ?)
/
10 (BF = 0, leaf)
Height(10) = 0 → BF(10) = (−1) − (−1) = 0
Height(20) = 1 → BF(20) = height(10) − height(null) = 0 − (−1) = 1
Height(40) = 0 → BF(40) = 0
Height(30) = 2 → BF(30) = height(20) − height(40) = 1 − 0 = 1 ✓ balanced| BF Value | Meaning | Action |
|---|---|---|
| −1, 0, +1 | Balanced | No action needed |
| +2 | Left-heavy (left subtree 2 taller) | LL or LR rotation |
| −2 | Right-heavy (right subtree 2 taller) | RR or RL rotation |
3. When and Why Rotations Happen
After inserting a node, we walk back up the tree updating heights and checking balance factors. The first ancestor with |BF| = 2 is the imbalanced node z. The rotation type depends on where the imbalance originated:
| Imbalanced Node z BF | Child y BF | Rotation Type | Rotations Performed |
|---|---|---|---|
| +2 (left heavy) | +1 (left heavy) | LL | Single right rotation at z |
| +2 (left heavy) | −1 (right heavy) | LR | Left rotation at y, then right rotation at z |
| −2 (right heavy) | −1 (right heavy) | RR | Single left rotation at z |
| −2 (right heavy) | +1 (left heavy) | RL | Right rotation at y, then left rotation at z |
4. LL Rotation (Single Right Rotation)
Trigger: New node inserted in the Left subtree of the Left child of the imbalanced node z.
Before LL Rotation: After Right Rotation at z:
z (BF=+2) y
/ \ / \
y T4 x z
/ \ / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
Steps:
1. y becomes the new subtree root.
2. z becomes y's right child.
3. y's old right subtree (T3) becomes z's new left child.Concrete Example: Insert 10, 20, 30
Insert 10: 10 BF(10)=0 ✓
Insert 20: 10 BF(10)=−1 ✓
\
20
Insert 30: 10 BF(10)=−2 ✗ (z=10, y=20, x=30 → RR case)
\ ... wait, this is RR not LL.
20
\
30
LL example — Insert 30, 20, 10:
Insert 30: 30
Insert 20: 30 BF=+1
/
20
Insert 10: 30 BF=+2 → LL rotation!
/
20
/
10
After right rotation at 30:
20
/ \
10 30 ← balanced ✓5. RR Rotation (Single Left Rotation)
Trigger: New node inserted in the Right subtree of the Right child of the imbalanced node z.
Before RR Rotation: After Left Rotation at z:
z (BF=−2) y
/ \ / \
T1 y z x
/ \ / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
Steps:
1. y becomes the new subtree root.
2. z becomes y's left child.
3. y's old left subtree (T2) becomes z's new right child.Concrete Example: Insert 10, 20, 30
Insert 10 → 20 → 30:
10 (BF=−2) ← z
\
20 (BF=−1) ← y
\
30 ← x
Left rotation at 10:
20
/ \
10 30 ← balanced ✓6. LR Rotation (Left-Right Double Rotation)
Trigger: New node inserted in the Right subtree of the Left child of z. The imbalance is “zig-zag left-right”.
Before LR: Step 1 (Left rotate at y): Step 2 (Right rotate at z):
z (BF=+2) z (BF=+2) x
/ / / \
y (BF=−1) x y z
\ /
x y
Steps:
1. Left-rotate at y → brings x up, y goes left of x.
2. Right-rotate at z → x becomes new root, z goes right of x.Concrete Example: Insert 30, 10, 20
Insert 30: 30
Insert 10: 30 (BF=+1)
/
10
Insert 20: 30 (BF=+2) ← z; left child 10 has BF=−1 → LR case!
/
10 (BF=−1) ← y
\
20 ← x
Step 1 — Left rotate at 10:
30
/
20
/
10
Step 2 — Right rotate at 30:
20
/ \
10 30 ← balanced ✓7. RL Rotation (Right-Left Double Rotation)
Trigger: New node inserted in the Left subtree of the Right child of z. The imbalance is “zig-zag right-left”.
Before RL: Step 1 (Right rotate at y): Step 2 (Left rotate at z):
z (BF=−2) z (BF=−2) x
\ \ / \
y (BF=+1) x z y
/ \
x y
Steps:
1. Right-rotate at y → brings x up, y goes right of x.
2. Left-rotate at z → x becomes new root, z goes left of x.Concrete Example: Insert 10, 30, 20
Insert 10: 10
Insert 30: 10 (BF=−1)
\
30
Insert 20: 10 (BF=−2) ← z; right child 30 has BF=+1 → RL case!
\
30 (BF=+1) ← y
/
20 ← x
Step 1 — Right rotate at 30:
10
\
20
\
30
Step 2 — Left rotate at 10:
20
/ \
10 30 ← balanced ✓8. Rotation Decision Table
| Insertion Sequence Pattern | BF at z | BF at y (child) | Rotation | Single/Double |
|---|---|---|---|---|
| z → left → left (e.g., 30,20,10) | +2 | +1 | LL (Right rotate z) | Single |
| z → right → right (e.g., 10,20,30) | −2 | −1 | RR (Left rotate z) | Single |
| z → left → right (e.g., 30,10,20) | +2 | −1 | LR (Left rotate y, Right rotate z) | Double |
| z → right → left (e.g., 10,30,20) | −2 | +1 | RL (Right rotate y, Left rotate z) | Double |
Insert went Left then Left → LL rotation. Insert went Right then Left → RL rotation.
9. Python Implementation
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(n):
return n.height if n else 0
def bf(n):
return height(n.left) - height(n.right) if n else 0
def update_height(n):
n.height = 1 + max(height(n.left), height(n.right))
def right_rotate(z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
update_height(z)
update_height(y)
return y # y is new subtree root
def left_rotate(z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
update_height(z)
update_height(y)
return y
def insert(root, key):
if not root:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
else:
return root # duplicate keys ignored
update_height(root)
balance = bf(root)
if balance > 1 and key < root.left.key: # LL
return right_rotate(root)
if balance < -1 and key > root.right.key: # RR
return left_rotate(root)
if balance > 1 and key > root.left.key: # LR
root.left = left_rotate(root.left)
return right_rotate(root)
if balance < -1 and key < root.right.key: # RL
root.right = right_rotate(root.right)
return left_rotate(root)
return root
# Usage
root = None
for k in [30, 20, 10]:
root = insert(root, k)
print(root.key) # 20 — after LL rotation10. GATE-Level Worked Examples
Example 1 — Identify Rotation Type (GATE 2020 pattern)
Solution:
Insert 5: 5 (BF=0) ✓
Insert 3: 5 (BF=+1) ✓
/
3
Insert 7: 5 (BF=0) ✓
/ \
3 7
Insert 1: 5 (BF=+1) ✓
/ \
3 7
/
1
Insert 4: 5 (BF=+2?) No — BF(5)=+1 still ✓
/ \
3 7 BF(3)=−1 (right child added)
/ \
1 4
Insert 2: BF(3)=+1 (left=1, right=4), BF(1)=−1 (right=2 added)
Wait — 2 inserts as right child of 1.
BF(3) recalculated: left height=1(node1,height1 after 2 added)=2?
Let's recalculate carefully:
After inserting 1,4 under 3: height(3)=2, height(5)=3, BF(5)=3-2=+1 (left=3nodes,h=2; right=7,h=1)
Insert 2 (right child of 1):
height(1)=1 → BF(1)= 0−1 = −1
height(3): left=1(h=1), right=4(h=0) → h=2, BF(3)= 1−0 = +1
height(5): left h=2, right h=1 → h=3, BF(5)= 2−1 = +1 ✓ no rotation needed
Final tree:
5
/ \
3 7
/ \
1 4
\
2 ← All BFs: 5(+1), 3(+1), 1(−1), others 0 → Balanced ✓
No rotation was needed for this sequence.
Example 2 — Minimum Nodes in AVL Tree of Height h (GATE theory)
Let N(h) = minimum nodes for AVL tree of height h.
N(0) = 1, N(1) = 2
N(h) = 1 + N(h−1) + N(h−2) (Fibonacci-like recurrence)
N(2) = 1+2+1 = 4
N(3) = 1+4+2 = 7
N(4) = 1+7+4 = 12
Example 3 — Which Rotation? (MCQ)
BF(z) = −2 (right heavy), BF(y) = +1 (left heavy).
This is the RL case.
Perform: right rotation at y, then left rotation at z.
Answer: RL (Right-Left double rotation)
11. Five Common Mistakes
Mistake 1 — Confusing rotation names with rotation direction
"LL rotation" means a right rotation (you rotate right to fix a left-left imbalance). Students often say "LL rotation = rotate left" — that's backwards. LL → right rotate; RR → left rotate.
Mistake 2 — Wrong height convention for null nodes
GATE uses height(null) = −1 (so a leaf has height 0). Some textbooks use height(null) = 0 (leaf has height 1). Be consistent within a problem. Mixing conventions gives wrong balance factors.
Mistake 3 — Forgetting to update heights after rotation
After any rotation, you must recalculate heights bottom-up (z first, then the new root). In code, if you update y's height before z's, you get stale values. Always update the lower node first.
Mistake 4 — Applying only one rotation for LR/RL cases
LR and RL imbalances require TWO rotations. Doing only the second rotation (right-rotate for LR, left-rotate for RL) without the first produces an incorrect tree that may still be unbalanced.
Mistake 5 — Assuming deletion also needs at most 1 rotation
Insertion needs at most 1 rotation. Deletion can propagate imbalance up the tree and may require O(log n) rotations, one per level. GATE sometimes tests this asymmetry explicitly.
12. Frequently Asked Questions
What is the balance factor in an AVL tree?
Balance Factor (BF) = height(left subtree) − height(right subtree). An AVL tree keeps BF ∈ {−1, 0, +1} for every node. When BF reaches +2 or −2 after an insertion or deletion, a rotation is performed to restore the AVL property.
When do you use LL, RR, LR, and RL rotations?
LL: BF(z)=+2, BF(left child)=+1 — single right rotation. RR: BF(z)=−2, BF(right child)=−1 — single left rotation. LR: BF(z)=+2, BF(left child)=−1 — left rotate child, then right rotate z. RL: BF(z)=−2, BF(right child)=+1 — right rotate child, then left rotate z.
What is the time complexity of AVL tree operations?
Search, insert, and delete are all O(log n) in the worst case. This is guaranteed because AVL trees maintain height ≤ 1.44 log₂(n+2). A plain BST degrades to O(n) for sorted input; AVL trees prevent this.
How many rotations does an AVL insertion require?
At most one rotation (single or double) per insertion. After the rotation, all ancestors' balance factors are restored automatically. Deletion may require up to O(log n) rotations — one per ancestor level — which is a key difference GATE tests.