Search code examples
data-structurestreeb-tree

the number of leaves of B tree of order 3

I am a new learner in data structure, and I am wondering how many leaves can a B tree of order-3 with height h have?

assuming the height of root is 1.

my opinion: when height is 1, the least of leaves are 2 (according to the definition), and the maximum of it is 3.

Then when it grows to 2, the maximum number of leaves becomes 6, then grows to 3, the maximum number of leaves becomes 9, and after that the number of leaves is always 9

could anyone help me out with this, please? thank you

Solution

  • I'll assume you use Knuth's definition of leaves, i.e. they are NIL nodes carrying no information, and Knuth's definition of order, i.e. the maximum number of children an internal node can have.

    my opinion: when height is 1, the[n] least of leaves are 2 (according to the definition), and the maximum of it is 3.

    Correct.

    Then when it grows to 2, the maximum number of leaves becomes 6

    ...only when the root has two children, but that is not the maximum. The root can have 3 children, and each of those children can have 3 leaves, so we have 3 x 3 = 9

    then grows to 3, the maximum number of leaves becomes 9, and after that the number of leaves is always 9

    Here I lost your logic... Each of the 9 leaves for trees of height 2 can be turned into an internal node with three new leaves, so we get 9 x 3 = 27 leaves

    The number of leaves is maximized by multiplying the number of leaves you have for one height less.

    So the formula is: max(#leaves) = 3h