I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

  • $t\ge 2$
  • Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
  • Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum_0^h (2t)^h(2t-1) $$

Does it have any convergence?

  • $\begingroup$ convergence doesn't seem to be the precise term. $\endgroup$
    – greybeard
    Feb 2 '20 at 7:52
  • $\begingroup$ @greybeard that was the closes term that I could think of. Maybe reduction?? $\endgroup$
    – Sab
    Feb 2 '20 at 7:59

Found it (using geometric serie for the sum)

$$\sum_{i=0}^h (2t)^i(2t-1) = (2t-1) \sum_{i=0}^h (2t)^i = (2t-1) \frac{(2t^{h+1}-1)}{(2t-1)} = (2t)^{h+1}-1 $$


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.