DSA AVL Trees
DSA AVL Trees – Complete Beginner Guide
(Concept • Rotations • Insertion • Example • Code • Complexity)
An AVL Tree is a self-balancing Binary Search Tree (BST).
It keeps the tree balanced automatically, ensuring fast operations even in the worst case.
1️⃣ What is an AVL Tree?
An AVL Tree is a BST where:
Balance Factor = Height(Left Subtree) − Height(Right Subtree)
For every node:
If balance factor goes outside this range, the tree rebalances itself using rotations.
2️⃣ Why AVL Tree is Needed
Normal BST can become skewed:
⏱ Operations become O(n) ❌
AVL Tree keeps height balanced, so:
3️⃣ AVL Tree Properties
✔ Follows BST property
✔ Automatically balances itself
✔ Height difference ≤ 1
✔ Uses rotations to rebalance
4️⃣ Balance Factor
| BF Value | Meaning |
|---|---|
| 0 | Perfectly balanced |
| +1 | Left heavy |
| -1 | Right heavy |
| > 1 or < -1 | ❌ Unbalanced |
5️⃣ AVL Tree Rotations (MOST IMPORTANT)
There are 4 imbalance cases:
1. LL Rotation (Left-Left)
Occurs when:
Insertion in left subtree of left child
Solution → Right Rotation
2. RR Rotation (Right-Right)
Occurs when:
Insertion in right subtree of right child
Solution → Left Rotation
3. LR Rotation (Left-Right)
Occurs when:
Insertion in right subtree of left child
Solution → Left Rotation + Right Rotation
4. RL Rotation (Right-Left)
Occurs when:
Insertion in left subtree of right child
Solution → Right Rotation + Left Rotation
6️⃣ AVL Rotations (Visual Logic)
| Case | Rotation |
|---|---|
| LL | Right Rotation |
| RR | Left Rotation |
| LR | Left → Right |
| RL | Right → Left |
7️⃣ AVL Tree Node Structure (C++)
8️⃣ Helper Functions
Height
Balance Factor
9️⃣ Rotations Code
Right Rotation (LL)
Left Rotation (RR)
🔟 AVL Tree Insertion
1️⃣1️⃣ Time Complexity
| Operation | Time |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
Guaranteed due to balancing.
1️⃣2️⃣ AVL Tree vs BST
| Feature | BST | AVL Tree |
|---|---|---|
| Balanced | ❌ No | ✅ Yes |
| Worst Case | O(n) | O(log n) |
| Rotations | ❌ No | ✅ Yes |
| Complexity | Simple | Complex |
1️⃣3️⃣ AVL Tree vs Red-Black Tree
| Feature | AVL | Red-Black |
|---|---|---|
| Strict Balance | Yes | Less strict |
| Rotations | More | Fewer |
| Search | Faster | Slightly slower |
| Insertion | Slower | Faster |
Interview Questions (AVL Trees)
Q1. Why AVL tree is faster than BST?
👉 Always balanced
Q2. What is balance factor?
👉 Height difference of subtrees
Q3. How many rotations in AVL?
👉 Four (LL, RR, LR, RL)
Final Summary
✔ AVL Tree is a self-balancing BST
✔ Balance factor ∈ {-1, 0, +1}
✔ Uses rotations to rebalance
✔ Guaranteed O(log n) operations
✔ Very important for advanced DSA & interviews
