What is an AVL Tree and how do rotations maintain balance?
ā Interview Prompt: Explain AVL Tree balance factor, single and double rotations (LL, RR, LR, RL), and O(log N) guaranteed height.
An AVL Tree is a self-balancing BST where the balance factor of every node = height(left) ā height(right) ā {ā1, 0, 1}.
Rotations to Restore Balance:
| Case | Imbalance | Fix |
|---|---|---|
| LL (Left-Left) | Node is right-heavy after left child insertion | Right Rotation |
| RR (Right-Right) | Node is left-heavy after right child insertion | Left Rotation |
| LR (Left-Right) | Left child's right subtree is heavy | Left Rotate child ā Right Rotate node |
| RL (Right-Left) | Right child's left subtree is heavy | Right Rotate child ā Left Rotate node |
AVL trees guarantee $O(\log N)$ height at all times, ensuring $O(\log N)$ search, insert, delete.
Code Implementation Example
// Right Rotation (LL case)
function rotateRight(y: TreeNode): TreeNode {
const x = y.left!;
const T2 = x.right;
x.right = y;
y.left = T2;
// Update heights after rotation
y.height = 1 + Math.max(height(y.left), height(y.right));
x.height = 1 + Math.max(height(x.left), height(x.right));
return x; // x is the new root
}
function height(node: TreeNode | null): number {
return node ? (node as any).height ?? 0 : 0;
}AVL Trees guarantee O(log N) at the cost of rotation overhead on insertions. Red-Black Trees (used in Java TreeMap, C++ std::map) have lighter balancing.