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 , so all operations are . Time: . Space: .