edited by
36,830 views
70 votes
70 votes

The following key values are inserted into a $B+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The $B+$ - tree is initially empty

$10$, $3$, $6$, $8$, $4$, $2$, $1$

The maximum number of times leaf nodes would get split up as a result of these insertions is

  1. $2$
  2. $3$
  3. $4$
  4. $5$
edited by

12 Answers

Best answer
75 votes
75 votes

In this question they have asked only to count leaf node splits.

So, after discussing with my friends on Facebook, I found that you will get two different answers depending on which convention you follow.

Convention 1: put the middle element in the left node, if you follow this you will get $4$ as answer.

Convention 2: put the middle element in the right node, if you follow this you will get $3$ as answer.

$4$ splits:

  1. after inserting $6$
  2. after inserting $4$
  3. after inserting $2$ (there will be an internal node split and a leaf node split)
  4. after inserting $1$

Correct Answer: $C$

edited by
35 votes
35 votes

Guys I hope everything is right with the right biased image, 

I hope the only thing that is mistakenly done by me IS

while insertion of 2, i have shown there are 2 splits .i.e. the 3rd split (leaf node split) and the 4th split (non-leaf node split) which all together should be considered as 1 single split only.

SO BASICALLY RIGHT BIASED has 3 splits.

THANK YOU

Correct me if I am wrong !!

edited by
11 votes
11 votes

i have tried to draw it and getting "4" split of leaf node using "left biasing"

correct me if you found any mistakes

8 votes
8 votes

answer is 3 if followed right biasing, means, putting middle element in right node.
and, answer is 4 if followed left biasing, means, putting middle element in left node.

but actually, which to follow officially ?
however, maximum is asked in this question, so ,there is a reason to choose left biasing here.

Answer:

Related questions

61 votes
61 votes
6 answers
1
30 votes
30 votes
2 answers
3