B-Tree Question

[coolbeanbob]

Hello All,

I just want to see if you have the correct answer for a homework problem. The question is to find the smallest number of entries that, when inserted in an appropriate order, will force a B-tree of order 5 to have 3 levels.

I believe the answer is 121. I don't think the order makes a difference, because the tree will just re-balance itself before it adds a level. Is this correct?

[Rashakil Fol]

> I don't think the order makes a difference, because the tree will just re-balance itself before it adds a level.

Try reading how rebalancing works and then reconsider your opinion.

Also your answer would be wrong regardless.

[coolbeanbob]

I'm trying to get a better understanding using this animation, but the "order" field seems to be different than the text from my book.

http://slady.net/java/bt/view.php

According to my book, order n means each node will have at most n children, each containing, at most, n-1 keys.

The animation shows a B-tree with order 1 to contain, at most, 3 keys per node.

[coolbeanbob]

Now I'm getting the answer is 17. Something tells me that is not right, but that is what I got when I walked through the algorithm.

[rubberman]

Actually, I think that the number of entries that will force 3 levels is 25 when the order is 5 (4 keys and 5 links to sub-nodes / node). So, level 1 will have 4 keys and 5 links, level 2 will have 5 nodes w/ 4 keys / node == 20 keys (24 total). So, a 25th key/entry will force a 3rd level, but only one partially filled node there. If you mean how many entries to create 3 full levels, then the number is 124:

Level 1 == 4 (1 node x 4 entries + 5 sub-nodes)
Level 2 == 20 (5 nodes x 4 entries + 25 sub-nodes)
Level 3 == 100 (25 nodes x 4 entries)

Which would be the case for a fully balanced tree.

[Narue]

Let's make it even more complicated. ;) B-Tree is an ambiguous term, and there are different versions that will wait until nodes are more full or less full before splitting.

[wadapav]

I think that 25 would be the correct answer for a 5 order tree to achieve level 3. This is because 4 keys in root and each 5 children has 4 keys each. So 24 in the first two levels to make it complete and 1 more to force the third level.
And I think generalized formula would be a summation as follows
(Summation from 0 to n-2 4*(5^k)) + 1 where n is the number of level you want to enforce

[coolbeanbob]

When I came up with 17, I had each leaf (3rd level or bottom level) containing two nodes. The max is four, but when the nodes split, two are remaining, and I am trying to do this with the LEAST possible entries.

Root === 1 node, 1 entry
Level 2 === 2 nodes, both containing 2 entries
Level 3 === 6 nodes, all containing 6 entries

[coolbeanbob]

I think that 25 would be the correct answer for a 5 order tree to achieve level 3. This is because 4 keys in root and each 5 children has 4 keys each. So 24 in the first two levels to make it complete and 1 more to force the third level.
And I think generalized formula would be a summation as follows
(Summation from 0 to n-2 4*(5^k)) + 1 where n is the number of level you want to enforce

What is k?

[rubberman]

It appears that you need to read Knuth, "The Art of Computer Programming" vol. 3, "Sorting and Searching", sections 6.2.3 and 6.2.4 on balanced and multi-way trees.

[coolbeanbob]

It appears that you need to read Knuth, "The Art of Computer Programming" vol. 3, "Sorting and Searching", sections 6.2.3 and 6.2.4 on balanced and multi-way trees.

It appears i am using the wrong book.

[coolbeanbob]

The correct answer was 17.