A rotation is a local rewrite that moves pointers and leaves every key in its in-order position, so it preserves the search-tree invariant automatically. Requiring |h_L − h_R| ≤ 1 at every node then forces a logarithmic height, because the smallest AVL tree of height h has N(h) = N(h−1) + N(h−2) + 1 nodes — Fibonacci growth, tabulated exactly rather than quoted as 1.44 log₂ n.
Core ideas
Two mechanical facts and one counting argument. The counting argument is the only place a new technique appears, and it is the same recurrence Fibonacci satisfies with a +1 bolted on.
Rotating right at x lifts x’s left child y into x’s place, hangs x as y’s right child, and re-parents y’s old right subtree as x’s new left subtree. Read the in-order sequence before and after: identical. No key changes its position in the sorted order, which is why the invariant cannot break and why every balanced tree in existence is allowed to use one.
|h_L − h_R| ≤ 1 is checked at a single node using two numbers stored there. Requiring it everywhere bounds the height of the whole tree, and the bound is proved by asking the opposite question: what is the fewest nodes a tree of height h can have while satisfying it? That count grows exponentially, so the height grows logarithmically.
A tree of height h satisfying the condition has one subtree of height h−1 and the other of height at least h−2, plus the root: N(h) = N(h−1) + N(h−2) + 1. That gives 1, 2, 4, 7, 12, 20, 33, 54, 88. To bound the height of a tree on n nodes, find the largest h with N(h) ≤ n — an exact integer comparison, which is what the lab does instead of evaluating 1.44 log₂ n.
The material
What a rotation does and does not change, where the recurrence comes from, and the table evaluated exactly beside the closed form.
A right rotation at a node x with left child y: y takes x’s place, x becomes the right child of y, and y’s former right subtree becomes x’s left subtree. A left rotation is the mirror image. Both are a fixed number of pointer writes.
A rotation requires the child it lifts to exist: there is no right rotation at a node with no left child, and the lab reports that as “not possible” rather than silently returning the tree unchanged — because a panel that could not tell those apart would show “in-order unchanged” as a success.
Let x have left child y, with subtrees A and B under y and C under x. In-order before: A, y, B, x, C. After a right rotation at x, y is the root with A on its left and x on its right, and x has B on its left and C on its right. In-order after: A, y, B, x, C.
The two sequences are the same symbol by symbol, so no key has changed its position in the sorted order and the search-tree invariant holds after if it held before. The heights do change, by at most one at each of the two nodes, and that is the entire point of performing one.
The lab draws both trees with the balance factor written above each node, and prints the two in-order sequences to be compared character by character. It also reports whether the rotation was possible at all. Try one at a node whose relevant child is missing and the panel says so, which matters because “nothing changed” and “the sequence was preserved” look identical from the outside.
Not every rotation shortens the tree. Rotating left at 30 in the tree built from 50 30 70 20 40 35 45 leaves the height at 3: the in-order sequence is preserved, the pointers moved, and the tree is no shorter. A rotation is a tool, not a repair; knowing which rotation to perform where is the next lesson.
A binary search tree in which, at every node, the heights of the two subtrees differ by at most 1. The difference h_L − h_R is the node’s balance factor, and it must be −1, 0 or 1 everywhere.
The height of an empty subtree is taken as −1 and of a leaf as 0. Every node stores its height, which is one extra integer and is what makes the condition checkable in constant time.
Let N(h) be the fewest nodes in an AVL tree of height h. Then N(0) = 1, N(1) = 2, and N(h) = N(h−1) + N(h−2) + 1.
A tree of height h has a subtree of height exactly h−1. The other subtree has height at least h−2, because the balance condition forbids a difference of 2 or more. To make the total as small as possible, take the smallest trees of those two heights, plus the root: that is the recurrence. Since N(h) + 1 is the Fibonacci number F(h+3), N(h) grows like φʰ, so a tree on n nodes has h ≤ log_φ n, which is about 1.44 log₂ n.
To bound the height of an AVL tree on n nodes, read up the N(h) column for the largest h whose entry is at most n. Six nodes: N(2) = 4 ≤ 6 and N(3) = 7 > 6, so the height is at most 2. A thousand nodes: N(13) = 986 fits and N(14) = 1596 does not, so the height is at most 13.
Compare that with the closed form. 1.44 log₂ 1000 is 14.35, so the closed form permits 14 where the exact table permits 13. Both are correct bounds and the table is tighter, which is why the lab evaluates the recurrence instead of the logarithm: the recurrence is integer arithmetic with nothing to round, and the constant 1.44 is itself a rounded 1/log₂ φ. Quoting 1.44 log₂ n is fine as a shape; using it as a number when an exact table is available is throwing away accuracy for no reason.
Interactive
A local rewrite that moves pointers and leaves the sorted order alone
Method
The rotation is mechanical and the bound is arithmetic. What needs care is checking each one rather than assuming it.
A right rotation needs a left child to lift; a left rotation needs a right child. Without it there is no rotation, and a tool that returns the tree unchanged in that case is indistinguishable from one that worked.
The child rises, the node becomes its child on the opposite side, and the child’s inner subtree re-parents onto the node. Write the three moves down rather than redrawing the tree from intuition — that is where the inner subtree gets dropped.
Symbol by symbol. They must be identical. This is the check that a rotation was performed rather than a tree rearranged, and it costs one line. Then look at the heights, which are the thing that was supposed to change.
Find the largest h with N(h) ≤ n. That is the bound for n nodes, and it is exact. Compare it with 1.44 log₂ n if you like, and expect the closed form to be looser — at n = 1000 it permits one level more than the table does.
The lab’s opening preset, with the three pointer moves written out and the table read for the tree that results.
The three pointer moves are the whole operation and the third is the one that gets forgotten. 30’s right subtree cannot stay with 30 — 30 now has 50 there — and it cannot go anywhere except 50’s left, because its keys are between 30 and 50. The in-order sequence forces it.
The table gives h ≤ 2 at six nodes and the rotated tree achieves it, which is a pleasant coincidence of this example rather than something a single rotation generally does. The pre-rotation tree had a balance factor of +2 at the root and was not an AVL tree at all; one rotation fixed it here because the imbalance was on the outside.
For a faded rehearsal, build 50 30 70 20 40 35 45 and rotate left at 30. The supplied observation is that the in-order sequence must be 20 30 35 40 45 50 70 before and after. Carry out the three moves, confirm the sequence, and note that the height is 3 both times: the rotation was legal, was performed, and did not shorten the tree. Then say what that means for a rule that has to choose which rotation to perform.
You should be able to rotate at a named node in either direction, state which child must exist for it to be possible, write both in-order sequences and confirm they match, tabulate N(h) from the recurrence, and read an exact height bound off the table for a stated n.
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.