The see-saw that keeps a tree from tipping over
Lesson 5 showed a BST can degrade into a chain. An AVL tree refuses to let that happen — after every insertion, it checks its balance and rotates itself back into shape.
After this lesson
You should be able to
- Compute a node's balance factor.
- Name the four rotation cases and which imbalance each fixes.
- Write a single right rotation.
Try it before you read
Try it live
Empty tree — insert a value to begin.
Recreate the problem yourself, first
Before reading further, use the tree below: reset it, then insert 10, 20, 30, 40, 50 in that order — plain sorted input, the exact case Lesson 5 warned about. What you get is a straight line pretending to be a tree, with search now costing as much as Unit I's linear list. That is the problem this lesson fixes.
Balance factor: the see-saw's reading
For any node, its balance factor is the height of its left subtree minus the height of its right subtree. In a healthy AVL tree, every single node's balance factor is -1, 0, or 1 — like a see-saw that is allowed to tilt slightly but never allowed to send one side crashing to the ground.
The moment an insertion pushes some node's balance factor to +2 or -2, that node is out of balance and must be fixed immediately, before returning further up the recursion.
Four shapes, four fixes
An imbalance always has one of four shapes, named by the path the extra height came in on. Left-Left: the new node went into the left subtree's left subtree — fixed by a single right rotation, pivoting the unbalanced node down and its left child up. Right-Right is the mirror image, fixed by a single left rotation.
Left-Right and Right-Left are the two-step cases: the extra height zigzags, going left then right, or right then left. Each needs two rotations — the first straightens the zigzag into a plain Left-Left or Right-Right shape, and the second is the single rotation you already know.
struct Node *rotate_right(struct Node *y)
{
struct Node *x = y->left;
struct Node *t = x->right;
x->right = y; /* x becomes the new top */
y->left = t; /* y takes x's old right subtree */
return x; /* caller must use this as the new subtree root */
}Try it yourself
Insert 30, 20, 10 into the tree below, one at a time, and describe by hand what a real AVL implementation would do after the third insertion — which node becomes unbalanced, and which single rotation fixes it.
Need a hint?
After inserting 10, trace the balance factor of 30, the root, specifically.
Check the worked solution
After 30 and 20, the tree is fine. Inserting 10 makes 30's left subtree two levels deeper than its (empty) right subtree — balance factor +2 at the root, with the extra height entering left-then-left. That is the Left-Left case: a single right rotation at 30 makes 20 the new root, with 10 as its left child and 30 as its right child — a balanced tree of height 1 instead of a chain of height 2. This widget does not animate the rotation itself; predicting it by hand is the exercise.
Quick check
A node's balance factor is left height 3, right height 1. What is the balance factor, and is the tree still valid AVL at this node?
Why this lesson exists
Syllabus mapping
AVL Trees
Maps to course outcomes CO2, CO4.