5k views

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 | 5k views

Max is asked, so we have to use left biasing which will give 4 leaf node splits. Thus ans C)

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

So after discussing with my friends on fb, 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$
edited by
Can you please draw the steps?

Yes, true but they have clearly asked MAXIMUM number of splits which would be achieved only using left biasing B+ tree. So, 4 is the only correct answer.

which order you are following , is it 3 or 2 .

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"
"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."
Read this statement from the question carefully. Both have same meaning.
So there cant be unique B tree , answers can be ambiguous

Those you want to visualize the tree. Draw the tree here by simply inserting the value. It will be right biased.

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

Which convention should be used while answering in GATE exam? convention 1 or Convention 2?
You're doing it completely wrong. Its clearly stated in question that order of internal node is maximum number of tree pointers in each node and they have given this order 3.

If there are 3 tree pointers then there must be 2 keys in each internal node. You have takes 3 keys in each internal node.

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

correct me if you found any mistakes

@prateek.. Yes u r correct but can u pl tell me what ans are u getting if we follow right biasing.. Bcz m getting 3..with right biasing also.. Am i correct?
Here, order is 3 so we can take only 2 key values in the internal nodes ,

so there should be split in the node having value 3, 4, 6 as in que --

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

so ans would be 4 only .

order of the internal nodes is 3 and order of internal nodes is the maximum number of tree pointers in each node

But at step 6, Your internal node has 4 poimters .

kapil plz help me out in this question
@Tauhin which part ?

kapil plz help in below question...

why the height of the tree will not decrease....???

https://gateoverflow.in/3537/gate2007-it-85

@prateek in ur ans at insert1 there are 2 split 123(at level 3)and 2346 (at level 2)

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain
@prateek

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....
internal node hav order 3 .. it means it will hav 2 keys ... y r u using 3 slots ??

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.

using left biasing the ans should be 4 but using right biasing 3. in ques it is not mention to use which biasing only mention isThe maximum number of times leaf nodes would get split up as a result of these insertions is so the correct ans should be only

answer according to geeks for geeks is 3. Plz suggest whether we should use right biasing or left biasing.

Ans: B

3 leaf  splits

1. after inserting 6

2. after inserting 8

3. after inserting 2

but at the tym of insertion of 6 only one node will be there so that must be considered as a root node , so why to count that..??
left biased 4 splits and right biased 3 splits... trying to add the image for it
edited

### SO BASICALLY RIGHT BIASED has 3 splits.

THANK YOU

Correct me if I am wrong !!

edited
leaf node will hav 2 keys ... and internal node will hav 2 keys as order is 3 ...
@puja ... is my diagram wrong? explain where did i go wrong?

leaf and internal nodes will hav 2 keys ...

3 splits

1. after inserting 10

2. after inserting 8

3. after inserting 2
How on this earth would 10 cause a split. That is the first value that get inserted in the tree !!!

I hope you are not confusing it with B- Tree.Because may result in 3 leaf node splits in this case but for B+ tree answer is 4 (as Vikrant said above).
It should be B . 3 leaf nodes

overall  3 leaf nodes + 1 Internal node
no it should be c