After an insertion, at most one node is out of balance — the lowest unbalanced ancestor — and one of four cases applies. The outside cases need a single rotation, the inside cases need two, and one fix restores balance all the way to the root. Ten keys in increasing order give height 3 with six rebalances, against 9 for the plain tree on the same order.
Core ideas
One decision procedure, one counting fact, and one thing that is genuinely surprising the first time: fixing a single node fixes the whole tree.
An insertion changes the height of nothing except the nodes on the path from the new leaf to the root, because every other subtree is untouched. So the repair walks back up that path, and the node to fix is the lowest one whose balance factor has reached ±2.
Look at the direction from the unbalanced node to its taller child, and then from that child toward the new key. Same direction twice — left-left or right-right — and one rotation suffices. Different directions — left-right or right-left — and one rotation moves the problem sideways rather than fixing it, so two are needed.
After the rebalance the subtree is exactly as tall as it was before the insertion, so every ancestor’s balance factor returns to what it was, and none of them needs anything. That is why an AVL insertion costs at most one single or one double rotation regardless of n, and it is a property of insertion specifically — deletion can need a rotation at every level, which is one reason this course states AVL deletion and does not develop it.
The material
Why the inside cases need two rotations, why one fix is enough, and what the measured heights are on the same insertion order.
Insert the key exactly as in a plain search tree: walk to where the search fails and attach a leaf. Then walk back up the path updating heights. If some node’s balance factor reaches +2 or −2, rebalance there and stop. The lowest such node is the one to fix, and there is at most one of them.
Suppose node z has balance +2 — its left subtree is two taller — and the new key went into the LEFT subtree of z’s left child. That is the LL case, and one right rotation at z fixes it: the left child rises, z drops to its right, and the two sides come out equal. RR is the mirror image, fixed by one left rotation.
Now suppose z has balance +2 and the new key went into the RIGHT subtree of z’s left child — the LR case. A single right rotation at z lifts the left child, but the offending subtree was on that child’s right, so it lands back on the left of z and the tree is now −2 the other way. The fix is to rotate the child left first, converting LR into LL, and then rotate z right.
The lab names the case at every rebalance and animates it. On the three-key sequences above it reports LL, LR and RL respectively, each with one rebalance, each ending at the same tree 20 with children 10 and 30 — the same final shape reached three different ways, which is worth seeing because it makes the case analysis feel less arbitrary.
After an AVL insertion, rebalancing the lowest unbalanced ancestor restores the invariant everywhere.
Before the insertion the subtree rooted at that node had some height h. The insertion made it h + 1, which is what unbalanced it. Both the single and the double rotation return the subtree to height h. So from that node upward nothing has changed height at all, and every ancestor’s balance factor is what it was before the insertion — which was legal. Hence one fix, at most two rotations, regardless of how tall the tree is.
Insert 1 through 10 in increasing order — the order that turns a plain search tree into a path. The lab runs both:
Every one of the six fixes is the RR case, because every key arrives larger than everything present. Height 3 against 9, on the input that is worst for the plain tree and costs the AVL tree six rotations — one per rebalance, since RR is a single rotation. The bound from the N(h) table is 3, and the tree reaches it.
A mixed order shows all four cases and a smaller gap. On the thirteen keys 50 25 75 10 5 30 27 60 90 80 70 98 62 the lab reports four rebalances — LL at 5, LR at 30, RR at 80, RL at 62 — giving height 3 against the plain tree’s 4, with 33 comparisons. The gap is one level, because that order was already reasonably balanced. Which is the caution: the measured benefit of balancing depends entirely on the order you measured it on, and the guarantee — h ≤ 1.44 log₂ n for every order — is the reason to pay for it.
Interactive
One fix at the lowest unbalanced ancestor restores the invariant everywhere
Method
Insert, then walk up, then name the case before rotating. Naming it first is what stops a double rotation being attempted as a single one.
The key goes where the search failed. Update the height at each node on the way back to the root and watch the balance factors. Stop at the first node — the lowest — whose factor reaches ±2.
From the unbalanced node to its taller child: left or right. From that child toward the new key: left or right. Same twice is LL or RR; different is LR or RL. The keys’ values play no part beyond telling you which way the walk went.
LL: rotate right at the unbalanced node. RR: rotate left. LR: rotate the left child left, then the node right. RL: rotate the right child right, then the node left. In the double cases the inner grandchild ends up as the subtree root, which is the thing to check afterwards.
One fix is enough: the subtree is back to its pre-insertion height, so no ancestor has changed. Confirm it by checking the balance factor at the parent of where you rotated — it should be what it was before the insertion, and if it is not, the rotation was wrong.
The LR case in full, because it is the one people attempt as a single rotation. Keys arriving 30, 10, 20.
The failed single rotation is the useful half of this example. Rotating 30 right lifts 10, but 20 was hanging on 10’s right, so it comes along and lands under 30 again — the tree is now left-light instead of left-heavy and is still illegal. The first rotation of the double exists to move 20 onto the outside, where a single rotation can reach it.
The inner grandchild ends as the subtree root. That is true of every double rotation and is the quickest way to check one: in the LR case the right child of the left child rises two levels. If something else ended up on top, the two rotations were done in the wrong order.
For a faded rehearsal, insert 10, 30, 20 — the RL case, the mirror of this one. The supplied observation is that it must end at the same tree, 20 with children 10 and 30, because there is only one AVL tree on three keys. Name the two rotations and their nodes, then run the lab’s ascending preset and say why all six of its rebalances are the same case.
You should be able to insert a key sequence by hand, identify the lowest unbalanced ancestor, name the case, perform the right number of rotations with the inner grandchild ending on top in the double cases, and say why one fix suffices for an insertion in terms of the subtree’s height.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.