- 2068 Magh · 5 marks
AVL tree for 24, 12, 8, 15, 35, ...
Short answer
Final AVL tree: root 24, left child 12 (left 8, right 15), right child 45 (left 35 with children 30 and 40, right 57 with right 78).
Create an AVL tree from the data: 24, 12, 8, 15, 35, 30, 57, 40, 45, 78.
Insert each key as in a BST and rebalance with rotations when a balance factor becomes ±2.
Balance factor of a node = height(left subtree) − height(right subtree). It must stay −1, 0 or +1. After each insertion, find the nearest unbalanced ancestor of the new node and fix it:
| Case | Where the new node went | Fix |
|---|---|---|
| LL | left subtree of left child | single right rotation |
| RR | right subtree of right child | single left rotation |
| LR | right subtree of left child | left rotation on the child, then right rotation |
| RL | left subtree of right child | right rotation on the child, then left rotation |
Step-by-step insertion
| Step | Insert | Tree after step (root(left,right)) | Imbalance / rotation |
|---|---|---|---|
| 1 | 24 | 24 | balanced |
| 2 | 12 | 24(12,-) | balanced |
| 3 | 8 | 12(8,24) | at 24: LL: right rotate at 24 |
| 4 | 15 | 12(8,24(15,-)) | balanced |
| 5 | 35 | 12(8,24(15,35)) | balanced |
| 6 | 30 | 24(12(8,15),35(30,-)) | at 12: RR: left rotate at 12 |
| 7 | 57 | 24(12(8,15),35(30,57)) | balanced |
| 8 | 40 | 24(12(8,15),35(30,57(40,-))) | balanced |
| 9 | 45 | 24(12(8,15),35(30,45(40,57))) | at 57: LR: left at 40, right at 57 |
| 10 | 78 | 24(12(8,15),45(35(30,40),57(-,78))) | at 35: RR: left rotate at 35 |
Final AVL tree
24
├─L:12
│ ├─L:8
│ └─R:15
└─R:45
├─L:35
│ ├─L:30
│ └─R:40
└─R:57
└─R:78
Height = 4, and every node has balance factor −1, 0 or +1.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- AVL tree for 10 20 30 50 45 40 8 5 3 · Data Structure and Algorithm, chapter 6
- AVL tree for 10, 20, 30, 35, 50, ... · Data Structure and Algorithm, chapter 6
- AVL tree for 52, 65, 72, 15, 11, 32, 20 · Data Structure and Algorithm, chapter 6
- AVL tree for 3, 2, 1, 4, 5, 6, 7, ... · Data Structure and Algorithm, chapter 6
- AVL tree for month names · Data Structure and Algorithm, chapter 6 · asked 2×
- B-tree insertion algorithm; AVL of months · Data Structure and Algorithm, chapter 6 · asked 2×
- EVA and S-curve; Rs 30,00,000, 24 months · Project Engineering, chapter 4
- Volume from central depths 1.85, 2.15, 2.45 · Surveying I, chapter 9