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

Okay. Might be resolution problem then. Image was actually well visible for me. I have now removed it and replaced with text.

---

If we are using right biased split(more elements on right after split) then answer will be $ 3$ else answer will be $5 $ so we need max of these and answer will be $5$

---

@Psy Duck For even order we prefer Right-biased only(right node will be having more nodes).

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

The middle element is always chosen during a split.

---

@Kuljeet Shan

we can take 2 or 3 as root .But the question asks for maximum number of splits which is possible only with 2 as root..

suppose we take 3 as root..then we have:

                  3

          1 2        4

now insert 5:

                  3

          1 2        45

Now insert 6:

                  3

          12        456 $----->$No splitting is done(which is not the case when you take 2 as root)

So you are missing a split which will not give you maximum splits at the end..

OR

If you want to take 3 as root and want maximum splits insert number<3 like 0 or -1 or -2... to get maximum splits

                  3

          1 2        4

Now insert 0:

                  3

         01 2        4

Now insert -1:

                           3

          -1 0 1  2        4 (overflow so split)

 after splitting:

   

                    1         3

          -1 0         2        4 

Now you won't miss any split ..

The main point is we try to populate the node which has maximum elements in order to get a split..

Hope this helps...

 

---

http://www.cburch.com/cs/340/reading/btree/index.html

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 can not apply biasing in b tree and we can apply biasing only in BPlus tree is it rite?

---

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.

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.