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 2 that represent {1, 2, 3, 4, 5}
The question asks for the legal trees with min degree t=2. So, each node can contain x num of keys while 1 ≤ x ≤ 3. Since each internal node that has x num of keys also has x+1 num of children (property 2), the root can only have 1 or 2 keys, the root can not have 3 keys since it must have 4 children and we only have 5 keys to draw.
If the root has 1 key there are following variations.
2
1 3 4 5 4
1 2 3 5 3
1 2 4 5If the root has 2 keys there is only one possibility.
2 4
1 3 5As 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.