- 2072 Asoj · 6 marks
AVL tree for 10, 20, 30, 35, 50, ...
Short answer
After insertions and rotations, the AVL tree is rooted at 35, with left child 20 (left 10, right 30) and right child 60 (left child 50 with left 40, right child 70 with left 65 and right 80).
Create an AVL balanced tree for the set of data 10, 20, 30, 35, 50, 70, 40, 80, 60, 65 by explaining each rotation rule used.
Insert each key as in a BST. Whenever a node gets balance factor ±2, apply the rotation for its case (LL, RR, LR or RL), stated in the table.
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 | 10 | 10 | balanced |
| 2 | 20 | 10(-,20) | balanced |
| 3 | 30 | 20(10,30) | at 10: RR: left rotate at 10 |
| 4 | 35 | 20(10,30(-,35)) | balanced |
| 5 | 50 | 20(10,35(30,50)) | at 30: RR: left rotate at 30 |
| 6 | 70 | 35(20(10,30),50(-,70)) | at 20: RR: left rotate at 20 |
| 7 | 40 | 35(20(10,30),50(40,70)) | balanced |
| 8 | 80 | 35(20(10,30),50(40,70(-,80))) | balanced |
| 9 | 60 | 35(20(10,30),50(40,70(60,80))) | balanced |
| 10 | 65 | 35(20(10,30),60(50(40,-),70(65,80))) | at 50: RL: right at 70, left at 50 |
Final AVL tree
35
├─L:20
│ ├─L:10
│ └─R:30
└─R:60
├─L:50
│ └─L:40
└─R:70
├─L:65
└─R:80
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 52, 65, 72, 15, 11, 32, 20 · Data Structure and Algorithm, chapter 6
- AVL tree for 24, 12, 8, 15, 35, ... · 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×
- Cutting volume, 60 m, GL 540.70, formation 538.20 · Surveying I, chapter 9 · asked 7×
- Three reservoirs ZA 65, ZB 70, ZC 40 · Hydraulics, chapter 3
- 3D rotation about axis (1,2,3)-(10,20,30) · Computer Graphics, chapter 4
- Elliptic: 2x2 grid 10/20/40/50 · Numerical Method, chapter 7 · asked 5×