1
$\begingroup$

the question goes as follows: In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)?

My idea:

Minimal: The root is 1, it has a minimum of 2 children, therefore we have 1 + 2, and then for any level below each node will have the minimum nodes allowed which is d. We get $1 + 2 + 2d + 2d^2 + ... + 2d^{h-1}$ including the leaves, therefore making $1 + \sum_{i=1}^{h-2} 2d^i$ (note that the final index is $h-2$ since we dont count the leaves).

Maximal: Pretty similiar but each level will have $2d$ children, thus making $ 1 + 2d + (2d)^2 + .... + (2d)^{h}$ including the leaves, therefore making $ \sum_{i=0}^{h-1} (2d)^i$.

However, the answer sheet goes $1 + \sum_{i=1}^{h} (2d)^i$ for maximal and $1 + \sum_{i=1}^{h} 2d^{i-1}$ for minimal.

I'll note that the height is defined as the numbers of edges from top-to-bottom, and for example; a tree of root only is of height 0. Tree of root + one set of children is of height 1.

Am I missing something or is there a mistake in our answer-sheet?

Thanks!

$\endgroup$
0
$\begingroup$

Update: There was an error in the answer sheet, it turns out I was right.

$\endgroup$
  • $\begingroup$ Probably best to delete the question, then, since it's no longer useful for you and unlikely to be of use to anyone in the future. $\endgroup$ – David Richerby May 28 '17 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.