For any B-tree of minimum degree t ≥ 2, every node other than the root must…
2013
For any B-tree of minimum degree t ≥ 2, every node other than the root must have atleast ________ keys and every node can have at most ________ keys.
- A.
t – 1, 2t + 1
- B.
t + 1, 2t + 1
- C.
t – 1, 2t – 1
- D.
t + 1, 2t – 1
Attempted by 168 students.
Show answer & explanation
Correct answer: C
Answer: Every non-root node must have at least t − 1 keys and at most 2t − 1 keys.
Reasoning:
Definition of minimum degree t: every internal node (except possibly the root) has at least t children and at most 2t children.
Number of keys = number of children − 1, so the minimum number of keys for a non-root node is t − 1.
Similarly, the maximum number of keys is 2t − 1 because the maximum number of children is 2t.
Special case: the root may have fewer than t − 1 keys; it can have as few as 1 key (or 0 keys in some definitions when the tree is empty) and at most 2t − 1 keys.