2.5AVL trees and rotations
The idea
An AVL tree is a BST that rebalances by rotations so that the heights of siblings differ by at most 1.
Think of it like this: A seesaw that nudges itself back level every time someone jumps on one side.
Why it exists
It guarantees O(log n) operations; GATE asks for the rotation type and the maximum height.
How it works
- Insert as in a BST, then walk back up and update heights.
- Find the lowest node with balance factor ±2.
- LL: rotate right. RR: rotate left.
- LR: rotate left at the child, then right. RL: the mirror.
Worked example: Insert 10, 20, 30
The root 10 gets balance −2 (an RR case): one left rotation makes 20 the root with children 10 and 30.
Now play with it
- →Switch to the AVL mode, insert sorted keys and watch the rotations in the step list.
- →Read the balance factors (small grey numbers).
(empty tree)
- empty tree
- insert 10
- insert 20
- insert 30: RR imbalance at 10: single left rotation
- insert 40
- insert 50: RR imbalance at 30: single left rotation
- insert 25: RL imbalance at 20: rotate right at 40, then left at 20
Inorder of a BST is always sorted. A plain BST built from sorted keys degenerates into a list (height n); the AVL tree keeps the height below 1.44 log₂ n. Numbers in grey are balance factors (left height − right height); red means a rotation is needed.
| Imbalance | Where the new key went | Fix |
|---|---|---|
| LL | left subtree of the left child | one right rotation at the unbalanced node |
| RR | right subtree of the right child | one left rotation |
| LR | right subtree of the left child | left rotation at the child, then right rotation |
| RL | left subtree of the right child | right rotation at the child, then left rotation |
Minimum nodes of an AVL tree: N(h) = N(h − 1) + N(h − 2) + 1, so heights 0, 1, 2, 3, 4, 5 need 1, 2, 4, 7, 12, 20 nodes.
Check yourself
Inserting 10, 20, 30, 40, 50, 25 into an AVL tree: the root of the final tree is
Exam notes (the dense version)
AVL = BST where every node has |height(left) − height(right)| ≤ 1. After an insert, rebalance the lowest unbalanced node: LL → right rotation, RR → left rotation, LR → left then right, RL → right then left. Height ≤ 1.44 log₂ n. Insertion needs at most one (single or double) rotation; deletion may need O(log n) rotations. The minimum number of nodes N(h) of an AVL tree of height h satisfies N(h) = N(h − 1) + N(h − 2) + 1.
Previous year questions: Trees & Binary Search Trees (15)
PYQs are grouped by topic, so this is the full set for Trees & Binary Search Trees; try the ones that match this subtopic. Open all 15 on the topic page.