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?
> 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.
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.
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.
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.
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.
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
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
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?
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 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.
The correct answer was 17.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.