AVL Tree Concept

An AVL tree maintains the balance factor at every node: $|height(left) - height(right)| \leq 1$.

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)$.