Geek asks and answers

The smallest number of leaves in a B Tree?

I am asked to prove that for a tree kB must be at least 2 (k + 1) ^ (h-1) .

From simple drawing of the fastest 3-B tree, I continue to get the tree to be at least 4 leaves, so that the tree reaches a height of 2, but 2 (k + 1) ^ (h-1) leads to 8 leaves.

Am I missing something?

+3
source share
1 answer

First, for typical B tree problems *, there are two types of nodes, your internal nodes and your leaf nodes. Thus, it is standard to indicate the maximum number of internal nodes, M and the maximum number of leaf nodes, L.

, M L , k, 3-B 2 ( h).

, . 2 (k + 1) ^ (h-1) , 8, node . node 2 , 8 . 4 .

:

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

* , , B +, B , B +.

+1

More articles:


All Articles