- Asked 2/14
- 2070 Magh · 4 marks
AVL tree for month names
Short answer
Final AVL tree: root mar; left child jan with left aug (apr, feb with left dec) and right jun (left jul); right child oct with left may (right nov) and right sep.
Create an AVL tree for the following data: jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec
Compare the month names in dictionary (alphabetical) order, so apr < aug < dec < feb < jan < jul < jun < mar < may < nov < oct < sep. Insert in the given order and rebalance 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 | jan | jan | balanced |
| 2 | feb | jan(feb,-) | balanced |
| 3 | mar | jan(feb,mar) | balanced |
| 4 | apr | jan(feb(apr,-),mar) | balanced |
| 5 | may | jan(feb(apr,-),mar(-,may)) | balanced |
| 6 | jun | jan(feb(apr,-),mar(jun,may)) | balanced |
| 7 | jul | jan(feb(apr,-),mar(jun(jul,-),may)) | balanced |
| 8 | aug | jan(aug(apr,feb),mar(jun(jul,-),may)) | at feb: LR: left at apr, right at feb |
| 9 | sep | jan(aug(apr,feb),mar(jun(jul,-),may(-,sep))) | balanced |
| 10 | oct | jan(aug(apr,feb),mar(jun(jul,-),oct(may,sep))) | at may: RL: right at sep, left at may |
| 11 | nov | mar(jan(aug(apr,feb),jun(jul,-)),oct(may(-,nov),sep)) | at jan: RR: left rotate at jan |
| 12 | dec | mar(jan(aug(apr,feb(dec,-)),jun(jul,-)),oct(may(-,nov),sep)) | balanced |
Final AVL tree
mar
├─L:jan
│ ├─L:aug
│ │ ├─L:apr
│ │ └─R:feb
│ │ └─L:dec
│ └─R:jun
│ └─L:jul
└─R:oct
├─L:may
│ └─R:nov
└─R:sep
Height = 5, and every node has balance factor −1, 0 or +1.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- B-tree insertion algorithm; AVL of months · Data Structure and Algorithm, chapter 6 · asked 2×
- 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 24, 12, 8, 15, 35, ... · Data Structure and Algorithm, chapter 6
- Describe an AVL tree · Data Structure and Algorithm, chapter 6
- AVL tree for 3, 2, 1, 4, 5, 6, 7, ... · Data Structure and Algorithm, chapter 6
- Advantages of AVL tree · Data Structure and Algorithm, chapter 6
- Annual firm and secondary energy (900 m³/s, Nov 650) · Hydro Power, chapter 3 · asked 2×
- Annual firm and secondary energy (900 m³/s, Nov 100) · Hydro Power, chapter 3 · asked 2×
- Installed capacity, energy and daily peaking reservoir (2079) · Hydropower Engineering, chapter 3 · asked 2×
- Installed capacity, energy and daily peaking reservoir (2072) · Hydropower Engineering, chapter 3 · asked 2×