B-tree insertion algorithm; AVL of months

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.

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

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.