The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
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$

 

asked in Databases by Veteran (69k points)
edited by | 5k views

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

9 Answers

+33 votes
Best answer
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$
answered by Veteran (14.1k points)
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.
+6 votes

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

correct me if you found any mistakes

answered by Veteran (10.4k points)
@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 ??
+3 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.

answered by (395 points)
+3 votes

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

answered by Boss (8.4k points)
answer according to geeks for geeks is 3. Plz suggest whether we should use right biasing or left biasing.
0 votes

Ans: B

3 leaf  splits

1. after inserting 6

2. after inserting 8

3. after inserting 2

answered by Loyal (2.6k points)
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..??
0 votes
left biased 4 splits and right biased 3 splits... trying to add the image for it
answered by Active (2.3k points)
edited by
0 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 !!

answered by Active (2.3k points)
edited by
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 ...

–2 votes
3 splits

1. after inserting 10

2. after inserting 8

3. after inserting 2
answered by Loyal (2.8k points)
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).
–2 votes
It should be B . 3 leaf nodes

overall  3 leaf nodes + 1 Internal node
answered by Junior (791 points)
no it should be c
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,230 answers
114,269 comments
38,798 users