CODEWITHSUNDEEP
data-structurestree
user1359417
user1359417

Reputation: 41

Least number of leaves in B Tree?

I'm being asked to prove that for a k-B tree, there must be at least 2(k + 1)^(h-1) leaves.

From just sketching out a quick 3-B tree myself, I keep getting there must be at least a minimum of 4 leaves for the tree to reach a height 2, but 2(k + 1)^(h-1) results in 8 leaves.

Am I overlooking something?

Upvotes: 3

Views: 3180

Answers (1)

lbrendanl
lbrendanl

Reputation: 2664

First off, for typical B tree problems*, there are two types of nodes, your internal nodes and your leaf nodes. Thus it is standard to both specify a max number of internal nodes, M, and a max number of leaf nodes, L.

But assuming you mean for M and L to be the same number, k, your min leafed 3-B tree of height 2 will indeed have only four leaves (assuming standard definition of height h).

I think that your problem is in the definition of the formula. 2(k + 1)^(h-1) will give you the minimum number of data elements in the leaves, which would have to be 8, since each leaf node must be at least half full. Therefore, each leaf node must have 2 elements in this example, giving you a total of 8 data elements in your tree. However you will only have 4 leaf nodes.

This is a good overview:

http://en.wikipedia.org/wiki/B%2B_tree

*I am assuming you are referring to what is technically a B+ tree, as B tree aren't used in practice, though everyone calls B+ trees B trees.

Upvotes: 1

Related Questions