The upper bound and lower bound for the number of leaves in a B-tree of degree…
2014
The upper bound and lower bound for the number of leaves in a B-tree of degree K with height h is given by :
- A.
\(K^{h}\)and\(2 \lceil \frac{k}{2} \rceil ^{h-1}\) - B.
\(K * h \)and\(2 \lfloor \frac{k}{2} \rfloor ^{h-1}\) - C.
\(K^{h}\)and\(2 \lfloor \frac{k}{2} \rfloor ^{h-1}\) - D.
\(K * h\)and\(2 \lceil \frac{k}{2} \rceil ^{h-1}\)
Attempted by 117 students.
Show answer & explanation
Correct answer: A
Solution:
Definitions and setup: Let K be the maximum number of children a node can have. Height h denotes the number of levels from the root down to the leaves (counting the root level as the first level).
Maximum number of leaves:
Each internal node can have at most K children, so the branching factor at each level is at most K. Starting from the root, after h levels the number of leaves is at most K^h.
Therefore, the upper bound on the number of leaves is K^h.
Minimum number of leaves:
The root, if it is not a leaf, must have at least 2 children.
Every other internal node must have at least ceil(K/2) children.
To minimize the number of leaves, use the smallest allowed branching at each internal level: the root contributes a factor of 2 and each of the remaining (h-1) levels contributes a factor of ceil(K/2).
Hence the lower bound on the number of leaves is 2 * ceil(K/2)^{h-1}.
Final answer: the number of leaves lies between 2 * ceil(K/2)^{h-1} and K^h (inclusive).