1
$\begingroup$

I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is:

Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum degree 2. How many nodes does the final B-tree have?

I think given that a node will have between $t-1$ and $2t-1$ keys, where $t$ is the minimum degree, so the answer for this question will be somewhere between $n$ and $n/3$? This is where I'm stuck, any help would be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ They want you to apply the algorithm and build the tree. $\endgroup$
    – Raphael
    Jan 31, 2018 at 12:47

1 Answer 1

3
$\begingroup$

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children.
If we imagine to construct a minimun nodes b-tree, we'll have:

$n = 1 + 2 + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$

where every addend is the number of nodes for every level, from the root (that can contains even one key), to the leaves level, and where h is the height of the b-tree;

If you consider the series, you have $n=1+2 \frac{ \lceil m/2\rceil^{h-1}-1}{\lceil m/2\rceil-1}$.

Instead, if you consider the maximum number of nodes, you will have:

$n= 1+m+m^2+...+m^{h-1} = \frac{m^h-1}{m-1}$.

where at the same way, every addend is the number of nodes for every level, and where h is the height of the b-tree;

You can easily find the result if you substitute 2 instead of m in the formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.