Questions: AVL Tree Rotations and Balancing

Question 1

After inserting a node into an AVL tree, a node has a balance factor of +2 and its left child has a balance factor of +1 (left-left case). How many pointer reassignments does the single right rotation require?

• A. O(log n) reassignments, since the rotation propagates up toward the root
• B. O(n) reassignments, since all nodes below must be updated
• C. A constant number of pointer reassignments, regardless of tree size
• D. O(height) reassignments, since each level on the path must be visited

Answer: (C)

Each rotation is O(1) — it reassigns a fixed, constant number of pointers among the three nodes involved and their subtrees. No other nodes need to be visited or updated. This is the central efficiency insight: rotations are cheap per-rotation, which is why AVL trees achieve O(log n) per operation overall. The common misconception that rotations propagate changes down the whole subtree confuses pointer reassignment with value propagation.

Question 2

A newly inserted node creates a left-right (LR) imbalance — the violation node's left child's right subtree is too tall. Why does a single right rotation at the violation node fail to fix this?

• A. Because LR imbalances require an O(n) correction pass
• B. A single rotation at the violation node moves the left child up, but the heavy part (the grandchild) ends up in the wrong position, effectively flipping the imbalance
• C. Single rotations only restore balance when the tree height is odd
• D. The LR case means no balanced configuration exists for that subtree

Answer: (B)

In the LR case, the 'heavy' subtree is the left child's right subtree — a zig-zag pattern. Rotating the violation node right promotes the left child, but the grandchild (the actual source of imbalance) ends up in the wrong position and the tree is still unbalanced. The fix is a double rotation: first rotate the left child left (converting LR to LL), then rotate the violation node right. A double rotation is just two single rotations composed — it is still O(1) total.

Question 3

Because AVL trees maintain O(log n) height and each rotation is O(1), all three core operations — search, insert, and delete — run in O(log n) worst-case time regardless of insertion order.

• T. True
• F. False

Answer: True

This is the core guarantee of AVL trees. The height is always O(log n) because the balance factor constraint (|height difference| ≤ 1) prevents one-sided degeneration. Search traverses at most O(log n) nodes. Insert applies at most one rotation (single or double) after the O(log n) traversal. Delete may require rotations at multiple ancestors as you walk up, but the path length is bounded by O(log n), and each rotation is O(1). The worst-case O(log n) guarantee holds for all three.

Question 4

When a node insertion into an AVL tree causes an imbalance, rotations should be performed at most ancestor node on the path from the new node to the root.

• T. True
• F. False

Answer: False

For insertion, at most one rotation (single or double) at the lowest violation point fully restores balance — no further rotations are needed at higher ancestors. The reason: a rotation restores the subtree to its pre-insertion height, so no ancestor's balance factor changes after the rotation. This distinguishes insertion from deletion: after deletion, rotations may propagate upward through multiple ancestors because the height reduction can continue affecting ancestors above the rotation point.

Question 5

Explain why the AVL balance requirement (|height difference| ≤ 1 at every node) guarantees O(log n) tree height, and why this matters for performance.

Model answer: The balance requirement prevents any subtree from becoming much taller than its sibling, forcing the tree to 'fan out' at every level. The minimum-size AVL tree of height h contains at least F(h+2) − 1 nodes (where F is Fibonacci), and Fibonacci numbers grow exponentially in h. Therefore h is at most ~1.44 log₂(n). Without the balance constraint, a BST can degenerate into a chain of height n, making every operation O(n).

The practical importance is that O(log n) vs O(n) is the difference between a structure that scales and one that doesn't. For n = 1,000,000, log₂(n) ≈ 20 but n = 1,000,000. The balance constraint ensures that even in adversarial insertion sequences (which would produce a chain in a plain BST), the AVL tree stays shallow. The cost is the bookkeeping — storing balance factors and checking after every insert/delete — but this constant overhead is worth the guarantee.