- 2071 Magh · 5 marks
AVL tree for 52, 65, 72, 15, 11, 32, 20
Short answer
Final AVL tree: root 52, left child 15 (left 11, right 32 with left 20), right child 65 (right 72).
Construct an AVL Tree for given integers: 52, 65, 72, 15, 11, 32, and 20.
Insert each key as in a BST and rebalance with rotations when a node's 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 | 52 | 52 | balanced |
| 2 | 65 | 52(-,65) | balanced |
| 3 | 72 | 65(52,72) | at 52: RR: left rotate at 52 |
| 4 | 15 | 65(52(15,-),72) | balanced |
| 5 | 11 | 65(15(11,52),72) | at 52: LL: right rotate at 52 |
| 6 | 32 | 52(15(11,32),65(-,72)) | at 65: LR: left at 15, right at 65 |
| 7 | 20 | 52(15(11,32(20,-)),65(-,72)) | balanced |
Final AVL tree
52
├─L:15
│ ├─L:11
│ └─R:32
│ └─L:20
└─R:65
└─R:72
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, 35, 50, ... · Data Structure and Algorithm, chapter 6
- AVL tree for 24, 12, 8, 15, 35, ... · 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 of order 3 for 52, 46, 27, ... · 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×
- 32:1 MUX tree; implement Σm(0,1,3,8,9,13,15) · Digital Logic, chapter 4
- Class C pool for 32, 65, 10, 21, 9 · Computer Networks and Security, chapter 4 · asked 2×
- 32:1 MUX tree from 4:1; implement Σ(0,1,3,8,9,13) · Digital Logic, chapter 4
- 1:32 DEMUX tree from 1:8 and 1:2 DEMUXes · Digital Logic, chapter 4