Trees

23 is larger than every key, so it belongs in the rightmost leaf (20, 21, 22). That leaf is full, and so are all the other leaves, so no key can be moved to a neighbour: the leaf must split, for example into (20, 21) and (22, 23), sending the separator 22 up to the root.

The root (6, 12, 19) is also full, so it splits too and a new root is created above the two halves. The tree grows from 2 levels to 3 and from 5 nodes to 8.

• (A) False: the leaf and the root both split.
• (B) True: each full node splits and its keys are shared between the two halves.
• (C) False: three nodes are added (a new leaf, the second half of the old root, and the new root).
• (D) True: the new root adds a level.

Answer: B, D

Let \(k\) be the number of nodes with two children; all other nodes are leaves. Count the edges in two ways:

• each of the \(k\) internal nodes has 2 child edges, giving \(2k\) edges;
• every node except the root has exactly one edge to its parent, giving \(n - 1\) edges.

So \(2k = n - 1\), that is, \(k = \frac{n-1}{2}\). For example, a root with two leaf children has \(n = 3\) and \(k = 1\). Such a tree always has an odd number of nodes, so \(\frac{n}{2}\) and \(\frac{n-2}{2}\) are not even whole numbers, while \(\frac{n+1}{2}\) counts the leaves.

Answer: B