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

I think you cannot change the order of insertion. Although your process is correct and if we follow left biasing with the given order of insertion as in question then also the answer would be 4.

---

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

---

Got trapped :(

Answer 1

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 2

I followed right biasing.

It Is giving 3 splits in leaf node. 

 

Answer 3

left biased 4 splits and right biased 3 splits... trying to add the image for it

Answer 4

If data is given in  either descending order or unsorted order  -  Left biasing will give Maximum leaf spilt...

If data is given in ascending order  -  Right biasing will give Maximum leaf split...

Here it is unsorted order... Therefore maximum leaf split = 4 by left biasing