GATE CSE 2008 | Question: 41

Question

A B-tree of order $4$ is built from scratch by $10$ successive insertions. What is the maximum number of node splitting operations that may take place?

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

Comments

It will be same @sreenadh annaluru

---

For Left bias 3 split and for right bias 5 split then we have give answer w.r.t right bias for this case.

---

Such a beautiful question.  Analysed correctly but in rush didnot split the root node at the end of 10th insertion. These silly mistakes are going to end me someday.

Answer 1

Total 5 splitting will occur during $10$ successive insertions

Let's take $10$ successive key values as $\{1,2,3,\ldots 10\}$ which can cause maximum possible splits.

 

 

Comments

I am getting 3 splits on doing left bias split how can i know whether to do left bias split or right bias split (although i am getting 5 spilits in right bias split) can someone please help me?

---

ig the only way is to consider both left and right biased splits and take whatever gives max.

Similar to this question

---

variation: what about minimum splits ? : i'm getting 2.

Answer 2

Let 1 to 10 be inserted

Insertion of 123 does not cause any split

When we insert 4 split occurs

We use right bias

              2

   1              3456

Again on insertion of 6 split occurs

             2 4

  1         3        56

7 does not cause split

           2 4  

1         3          5678

8 cause  split

       2  4   6

1       3    5    7 8

Inserting 9 wont cause any split

       2  4   6

1       3    5    7 8 9

Inserting 10 causes split at leaf and non leaf node

           4

    2          6   8

1    3    5   7    9 10

So total 5 splits

Comments

we choose 2nd element because we want right bias[more element on right side] , if you want left bias[more element on left side] .then you can . no restriction .

---

@Kaluti please share reference for your statement. I think both trees support biasing.

---

Caption

 

Answer 3

In this ques we can splits a node with two methods which is based on chosing mid element  ,

1-Right bias (#keys in right > #keys in left or  choosing mid elem is N/2 th element ) ,then no SPLITS =5

 2-Left bias (#keys in left > #keys in left or  choosing mid elem is (N/2 +1) th element) ,then no SPLITS =3  ,where N is even.

   so, MAX # splits = 5 .

Ans is C:5

Comments

No, left biased will also produce 5 splitting operations maximum..

U are saying left bias will split 3 times as you have taken some special set of sorted inputs like 1,2,3,4,5,6,7,8,9,10  i guess,

But try this input combination 10,20,30,40,28,29,26,27,24,25 and perform left biased splitting on it.. U will get maximum splitting as 5

Answer 4

Answer: C

Insert 10,20,30,40,5,6,15,12,17,13 (in that order). You will get five splittings.

Answer 5

start inserting from 1 to 10 in a b-tree you will end up splitting it 5 times

1^st split  :while inserting 4

2^nd split :while inserting 6

3^rd split:while inserting 8

4^th and 5th split :while inserting 10

Answer 6

ans 3

Comments

what is the rule for splitting , because minimum way I can split the node is 3 and the maximum way is 8

---

thanks @Sriram Karunagaran, :)

---

Split would be required when key items=4

If i put n/2th element in the upper level while splitting, then splits=5

Otherwise put (n/2+1) th element in upper level, then split=3