Why do AVL rotations actually work?
Rotations felt like magic until I realized they are just a way to re-pick the root of a small subtree while keeping BST order.
Take the right-right case: A has right child B, and B has right child C. The subtree leans right. A single left rotation makes B the new root, with A as its left child and C as its right child.
Why is order preserved? Everything in B's old left subtree is bigger than A but smaller than B, so it slots in perfectly as A's new right subtree. Nothing crosses the BST boundary.
Why does height shrink? The long path A → B → C becomes B with two children of equal height, so the imbalance disappears.
Double rotations are the same idea when the heavy grandchild is on the "inside": rotate the child first to turn it into the straight-line case, then rotate the root. Once I drew all four cases side by side, I stopped memorizing and started seeing.
Comments
The "re-pick the root while keeping BST order" framing finally made it click for me. Thank you!
Drawing the four cases side by side is the move. I did the same with colored pens.
Could you add how the balance factors change after a double rotation? That's the part I still fumble.