AVL Tree
A self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
A self-balancing Binary Search Tree (BST) named after its inventors Adelson-Velsky and Landis. It maintains O(log n) height by automatically performing rotations during insertion and deletion if the tree becomes unbalanced.
Concept
In a normal BST, skewed data (like 1, 2, 3, 4...) can degrade performance to O(n). AVL Trees fix this by tracking a Balance Factor (Left Height - Right Height) for every node. If |BF| > 1, it rotates to restore balance.
How it Works
- Balance Factor (BF): Height(Left) - Height(Right).
- Valid BF: -1, 0, 1.
- Rotations: Operations to fix imbalance:
- LL Cases: Right Rotation.
- RR Cases: Left Rotation.
- LR Cases: Left then Right Rotation.
- RL Cases: Right then Left Rotation.
Step-by-Step Breakdown
- Insert node like standard BST.
- Backtrack up to root, updating heights.
- Check Balance Factor of each node.
- If Node becomes unbalanced (|BF| > 1):
- Left-Left (LL): Perform Right Rotation.
- Right-Right (RR): Perform Left Rotation.
- Left-Right (LR): Left Rotate left child, then Right Rotate current.
- Right-Left (RL): Right Rotate right child, then Left Rotate current.
When to Use
- Database indexing where lookups must be fast O(log n).
- Symbol tables in compilers.
- When search operations are more frequent than insertions/deletions.
When NOT to Use
- When insertions/deletions are very frequent (Red-Black trees might be slightly better due to fewer rotations).
- Simple scenarios where O(n) worst case is acceptable.
How to Identify
Key requirements: "Balanced BST", "Guaranteed O(log n) search", "Rotations".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.