retagged by
976 views
0 votes
0 votes
An order 3 B-tree is an index tree where every node other than root has at most 2 keys and at least one key. Starting with an empty tree if following keys are inserted into the tree 1,2,3,4,5,6,7,8,9,10. (not necessarily in the given order.) What would be the minimum number of node splits possible, if node splitting algorithm is used?
retagged by

1 Answer

2 votes
2 votes

Insert in such a way that it will build as Full B- Tree since Order given 3 so we can insert at most 2 keys per node.

Full B- Tree contains root with 1 element, left subtree with 4 or 5 elements, right subtree with 4 or 5 elements.

For 10 nodes height is 3 so only 3 splits needed. 

NOTE: Always Select a middle element for new Insert.

Related questions

1 votes
1 votes
0 answers
1
thor asked Jan 7, 2017
548 views
What should be the insertion order of elements such that the following B+ Tree is obtained? (order of root node = 3, and leaf node = 2)
18 votes
18 votes
1 answer
2
Akanksha Kesarwani asked Dec 10, 2016
6,280 views
Difference between left biasing and right biasing in B+ tree insertion, Rules to be followed for left and right biasing , Kindly explain with an example ?