edited by
21,479 views
50 votes
50 votes

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?

  1. $3$
  2. $4$
  3. $5$
  4. $6$
edited by

6 Answers

Best answer
69 votes
69 votes

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.

 

 

edited by
23 votes
23 votes

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

10 votes
10 votes
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
Answer:

Related questions