--- title: "AVL tree for month names" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:avl-build-months" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-build-months site: BCT Engineering --- # AVL tree for month names Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2070 Magh, 4 marks - Video: [AVL Tree Construction example](https://www.youtube.com/watch?v=DAONI4zKYbA) — StudyKorner - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-build-months - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Create an AVL tree for the following data: jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec ## 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. ## Answer 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 ```text 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How are the month names ordered when building this AVL tree? A. By calendar order, so jan is the smallest B. Alphabetically (dictionary order), so apr is the smallest C. By length of the name, shortest first D. By the order of insertion only Answer: B. The keys are strings, so the answer compares them in dictionary order: apr < aug < dec < feb < jan < jul < jun < mar < may < nov < oct < sep. (Key point: Comparison order) 2. What is the balance factor of a node and which values are allowed in an AVL tree? A. height(right) + height(left); any value up to 3 B. Number of left nodes minus number of right nodes; only 0 C. height(left) - height(right); only 0 or 1 D. height(left) - height(right); only -1, 0 or +1 Answer: D. The balance factor is the left height minus the right height and must stay -1, 0 or +1. A rotation is needed when it becomes +2 or -2. (Key point: Balance factor) 3. When aug is inserted (step 8), feb becomes unbalanced. Which case and fix apply? A. LL: a single right rotation at feb B. LR: left rotation at apr, then right rotation at feb C. RR: a single left rotation at feb D. RL: right rotation at mar, then left rotation Answer: B. aug < feb but aug > apr, so it enters the right subtree of feb's left child: an LR case, fixed by a double rotation (left at apr, right at feb). (Key point: LR case at insertion of aug) 4. Inserting nov (step 11) unbalances jan. What happens and what becomes the new root? A. LL case; right rotation at jan keeps jan as root B. No rotation is needed because the tree stays balanced C. RL case; the root becomes oct D. RR case; left rotation at jan makes mar the root Answer: D. nov goes into the right subtree of jan's right child, so a single left rotation at jan is done, and mar becomes the root of the tree. (Key point: RR rotation when nov is inserted) ## Close variants set in other exams - [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2× ## Related in Data Structure and Algorithm - [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6 - [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6 - [AVL tree for 24, 12, 8, 15, 35, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-24-12-8) — Data Structure and Algorithm, chapter 6 - [Describe an AVL tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-describe) — Data Structure and Algorithm, chapter 6 - [AVL tree for 3, 2, 1, 4, 5, 6, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-3-2-1-4) — Data Structure and Algorithm, chapter 6 - [Advantages of AVL tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-advantage) — Data Structure and Algorithm, chapter 6 ## Related in other subjects - [Annual firm and secondary energy (900 m³/s, Nov 650)](https://www.bctengineer.com/question.md?key=semester_6%2Fhydro_power%3Afirm-secondary-energy-2079) — Hydro Power, chapter 3, asked 2× - [Annual firm and secondary energy (900 m³/s, Nov 100)](https://www.bctengineer.com/question.md?key=semester_6%2Fhydro_power%3Afirm-secondary-energy-2078) — Hydro Power, chapter 3, asked 2× - [Installed capacity, energy and daily peaking reservoir (2079)](https://www.bctengineer.com/question.md?key=semester_7%2Fhydropower_engineering%3Aror-capacity-plant-factor-18cumec-peaking-79) — Hydropower Engineering, chapter 3, asked 2× - [Installed capacity, energy and daily peaking reservoir (2072)](https://www.bctengineer.com/question.md?key=semester_7%2Fhydropower_engineering%3Aror-capacity-plant-factor-18cumec-peaking-72) — Hydropower Engineering, chapter 3, asked 2×