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.
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−1keys 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 ≤ 2 and 2 t – 1 ≥ 3,
which yields 2 ≤ t ≤ 3. So t can be 2 or 3.
Show all legal B-trees of minimum degree 3 that represent {1, 2, 3, 4, 5}
We know that every node except the root must have at least t – 1 = 2 keys, and at most 2t – 1 = 5 keys. Also remember that the leaves stay in the same depth. Thus, there are 2 possible legal B-trees:
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?
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.
Follow @louis1992 on github to help finish this task.