18.1 Definition of B-trees

18.1-1

Why don't we allow a minimum degree of $t = 1$?

According to the definition, minimum degree $t$ means every node other than the root must have at least $t - 1$ keys, and every internal node other than the root thus has at least $t$ children. So, when $t = 1$, it means every node other than the root must have at least $t - 1 = 0$ key, and every internal node other than the root thus has at least $t = 1$ child.

Thus, we can see that the minimum case doesn't exist, because no node exists with $0$ key, and no node exists with only $1$ child in a B-tree.

18.1-2

For what values of $t$ is the tree of Figure 18.1 a legal B-tree?

According to property 5 of B-tree, every node other than the root must have at least $t - 1$ keys and may contain at most $2t - 1$ keys. In Figure 18.1, the number of keys of each node (except the root) is either $2$ or $3$. So to make it a legal B-tree, we need to guarantee that $t - 1 \le 2 \text{ and } 2 t - 1 \ge 3$, which yields $2 \le t \le 3$. So $t$ can be $2$ or $3$.

18.1-3

Show all legal B-trees of minimum degree $2$ that represent $\{1, 2, 3, 4, 5\}$.

Since $t=2$, every node (except the root) must have at least $t-1=1$ key and at most $2t-1=3$ keys.

• Root $2$:

  $$ \begin{array}{c} |\,2\,| \\[6pt] \swarrow \qquad \searrow \\[6pt] |\,1\,| \qquad |\,3,4,5\,| \end{array} $$

• Root $3$:

  $$ \begin{array}{c} |\,3\,| \\[6pt] \swarrow \qquad \searrow \\[6pt] |\,1,2\,| \qquad |\,4,5\,| \end{array} $$

• Root $4$:

  $$ \begin{array}{c} |\,4\,| \\[6pt] \swarrow \qquad \searrow \\[6pt] |\,1,2,3\,| \qquad |\,5\,| \end{array} $$

• Root $2, 4$:

  $$ \begin{array}{c} |\,2,4\,| \\[6pt] \swarrow \qquad \downarrow \qquad \searrow \\[6pt] |\,1\,| \qquad |\,3\,| \qquad |\,5\,| \end{array} $$

18.1-4

As a function of the minimum degree $t$, what is the maximum number of keys that can be stored in a B-tree of height $h$?

$$ \begin{aligned} n & = (1 + 2t + (2t) ^ 2 + \cdots + (2t) ^ {h}) \cdot (2t - 1) \\ & = (2t)^{h + 1} - 1. \end{aligned} $$

18.1-5

Describe the data structure that would result if each black node in a red-black tree were to absorb its red children, incorporating their children with its own.

After absorbing each red node into its black parent, each black node may contain $1, 2$ ($1$ red child), or $3$ ($2$ red children) keys, and all leaves of the resulting tree have the same depth, according to property 5 of red-black tree (For each node, all paths from the node to descendant leaves contain the same number of black nodes). Therefore, a red-black tree will become a Btree with minimum degree $t = 2$, i.e., a 2-3-4 tree.