- 2073 Magh · 4 marks
AVL tree for 3, 2, 1, 4, 5, 6, 7, ...
Short answer
The final AVL tree has root 7, left child 4 (left child 2 with left 1 and right 3, right child 6 with left 5), and right child 15 (left child 13 with left 12 and right 14, right 16).
Construct an AVL tree for the following sequence of elements: 3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12
Insert each key as in a BST and fix any node whose balance factor becomes ±2 by rotation.
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 | 3 | 3 | balanced |
| 2 | 2 | 3(2,-) | balanced |
| 3 | 1 | 2(1,3) | at 3: LL: right rotate at 3 |
| 4 | 4 | 2(1,3(-,4)) | balanced |
| 5 | 5 | 2(1,4(3,5)) | at 3: RR: left rotate at 3 |
| 6 | 6 | 4(2(1,3),5(-,6)) | at 2: RR: left rotate at 2 |
| 7 | 7 | 4(2(1,3),6(5,7)) | at 5: RR: left rotate at 5 |
| 8 | 16 | 4(2(1,3),6(5,7(-,16))) | balanced |
| 9 | 15 | 4(2(1,3),6(5,15(7,16))) | at 7: RL: right at 16, left at 7 |
| 10 | 14 | 4(2(1,3),7(6(5,-),15(14,16))) | at 6: RL: right at 15, left at 6 |
| 11 | 13 | 7(4(2(1,3),6(5,-)),15(14(13,-),16)) | at 4: RR: left rotate at 4 |
| 12 | 12 | 7(4(2(1,3),6(5,-)),15(13(12,14),16)) | at 14: LL: right rotate at 14 |
Final AVL tree
7
├─L:4
│ ├─L:2
│ │ ├─L:1
│ │ └─R:3
│ └─R:6
│ └─L:5
└─R:15
├─L:13
│ ├─L:12
│ └─R:14
└─R:16
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 24, 12, 8, 15, 35, ... · 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 10 20 30 50 45 40 8 5 3 · Data Structure and Algorithm, chapter 6
- B-tree properties; order 5 for 3, 14, 7, ... · Data Structure and Algorithm, chapter 6 · asked 2×
- 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×
- K-map Σm(7,9,12,13,14,15)+d, NOR-only · Digital Logic, chapter 3
- Minterms/maxterms; K-map Σm(0,1,2,4,6,8,9,12,13,14) · Digital Logic, chapter 3
- 32:1 MUX tree; implement Σm(0,1,3,8,9,13,15) · Digital Logic, chapter 4
- Standard error; population 12,19,13,16 · Probability and Statistics, chapter 4