跳转至

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\\}\).

We know that every node except the root must have at least \(t - 1 = 1\) keys, and at most \(2t - 1 = 3\) keys. Also remember that the leaves stay in the same depth. Thus, there are \(2\) possible legal B-trees:

  • \[| 1, 2, 3, 4, 5 |\]
  • \[| 3 |\]
    \[\swarrow \quad \searrow\]
    \[| 1, 2 | \qquad\qquad | 4, 5 |\]

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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用