GATE CSE 2009 | Question: 44

Question

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

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Comments

suggestion before marking the answer check for both left biasing and right biasing because we have to find the maximum leaf splits.

---

Got trapped :(

---

It's asking the maximum number of times so the answer will be 4

Answer 1

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$

Comments

In this type of question do we need to work out both left biased and right biased approach ?

---

does the order of leaf node mean number of keys, i got a little confused because I think for non leaf nodes order means the max number of child pointers...

---

@Soumyabrata Chatterj Yes, we need to do it.

Answer 2

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 !!

Comments

Both Left and right biased diagram are correct.

In right step 6 is 2 split one is from leaf and second one is from internal node.

---

Can u please share your whole notes pdf?

---

You don’t need to completely draw the tree. We are only required to calculate splits at leaf nodes. So, we can just draw leaf nodes, and split them, whenever necessary, no need to draw the tree above that as we don’t care what happens in the internal nodes. It would save you so much time in such a question if it comes in exam.

Answer 3

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

correct me if you found any mistakes

Comments

@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 ??

---

@prateek in the question it is asked max no of splits at leaf nodes, you are counting even split at non-leaf node.

Answer 4

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.

Comments

This answer makes more sense

Answer 5

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 4 only

Comments

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

Answer 6

I followed right biasing.

It Is giving 3 splits in leaf node.