An AVL tree maintains the balance factor at every node: .
When insertion or deletion violates this, rotations restore balance: Left Rotation (right-heavy):
x y
\ / \
y → x z
\
z
Right Rotation (left-heavy):
x y
/ / \
y → z x
/
z
``` Double rotations handle zig-zag cases:
- Left-Right rotation: left rotate child, then right rotate node
- Right-Left rotation: right rotate child, then left rotate node
AVL trees guarantee $h = O(\log n)$, so all operations are $O(\log n)$. Time: $O(h)$. Space: $O(h)$.