---
title: "B-tree insertion algorithm; AVL of months"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:btree-insertion-avl-months"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/btree-insertion-avl-months
site: BCT Engineering
---

# B-tree insertion algorithm; AVL of months

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2071 Bhadra, 6 marks
- Video: [B-Tree Data Structure Explained with Animations | Insertion, Deletion & Search](https://www.youtube.com/watch?v=JDZfrwjja8A) — Algopk
- 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/btree-insertion-avl-months
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Write an algorithm for the insertion of B-Tree. Create an AVL tree for the following data: jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec

## Short answer

B-tree insertion: search to leaf, insert key; if node overflows (m keys), split by moving median to parent, splitting node into two. Repeat up to root if needed. AVL tree for months: root mar, left jan (left aug with apr and feb with left dec, right jun with left jul), right oct (left may with right nov, right sep).

## Answer

#### Algorithm for insertion in a B-tree
A B-tree of order m has at most m children (m − 1 keys) per node, every internal node other than the root has at least ⌈m/2⌉ children (the root has at least 2 unless it is a leaf), and all leaves are on the same level. Insertion always happens in a leaf; the tree grows upward by splitting.

```text
BTreeInsert(root, key)        /* order m: max m-1 keys, min ceil(m/2)-1 keys */
1. If the tree is empty, create a root node with the key; stop.
2. Search from the root down to the leaf where key belongs
   (at each node follow the child between the two keys that surround key).
   If key is found already, stop (no duplicates).
3. Insert key into that leaf in sorted order.
4. While the current node has m keys (overflow):
      a. Find the median key (middle of the m keys).
      b. Split the node into two nodes: keys before the median stay in
         the left node, keys after the median go to a new right node.
      c. Move the median up into the parent, between the pointers
         to the two halves.
      d. If the node was the root, create a new root holding only the
         median (the tree grows one level taller); stop.
      e. Otherwise make the parent the current node and repeat.
5. Stop.
```

The cost is O(log n) node accesses because the height is O(log n).

#### AVL tree for the month names
Months are compared alphabetically (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.

#### 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. In the B-tree insertion algorithm, where is a new key first placed?
   A. In the appropriate leaf, in sorted order
   B. In the root, then pushed down
   C. In a new leaf at the bottom of the tree always
   D. In the internal node whose key is closest in value
   Answer: A. Insertion always happens in a leaf found by searching down from the root; the tree grows upward by splitting. (Key point: Where B-tree insertion happens)

2. What happens when a node reaches m keys (overflow) after insertion?
   A. The smallest key is deleted to make space
   B. The whole tree is rebuilt
   C. It is split at the median key, and the median moves up to the parent
   D. The node keeps m keys and children are added
   Answer: C. The node is split into a left and right half and the median key goes into the parent between the two halves. (Key point: Overflow and split)

3. What happens if the node that splits is the root?
   A. A new root holding only the median is created and the tree grows one level
   B. The tree height decreases by one
   C. The median is discarded
   D. The two halves are merged again
   Answer: A. When the root splits there is no parent, so a new root with the median key is created and the height increases by one. (Key point: Root split)

4. In the AVL part, inserting oct unbalances may. Which fix is used?
   A. LL: single right rotation at may
   B. RR: single left rotation at may
   C. RL: right rotation at sep, then left rotation at may
   D. LR: left rotation at may, then right rotation
   Answer: C. oct is inserted to the left of sep, which is the right child of may, so it is an RL case needing a double rotation. (Key point: RL case for oct)

## Close variants set in other exams

- [AVL tree for month names](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-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
- [Heap tree insertion and heap sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-insertion-and-sort) — Data Structure and Algorithm, chapter 7
- [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

## 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×
- [Firm and secondary energy from average monthly flows](https://www.bctengineer.com/question.md?key=semester_6%2Fhydro_power%3Afirm-secondary-energy-2075) — Hydro Power, chapter 3
- [Peaking RoR: max power and wet/dry energy ratio](https://www.bctengineer.com/question.md?key=semester_7%2Fhydropower_engineering%3Apeaking-ror-reservoir-250m-q25) — Hydropower Engineering, chapter 3