Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
