185. Explain the four AVL rebalancing cases and their rotations.
HardTrees
Technical
Show model answer
A node becomes unbalanced when its children's heights differ by 2. Left-Left (the extra height is in the left child's left subtree): one right rotation at the node. Right-Right: one left rotation. Left-Right: first rotate the left child left, then rotate the node right. Right-Left: rotate the right child right, then the node left.
Each rotation re-links a constant number of pointers and recomputes two heights, so it is O(1). After an insertion, rebalancing the lowest unbalanced ancestor (with one single or double rotation) restores balance for the whole tree. A deletion may require rotations at several ancestors, up to O(log n), so both operations remain O(log n).
What interviewers listen for
- LL: right rotate. RR: left rotate. LR: left then right. RL: right then left.