## 5 Answers

### 9 Comments

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...

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

### 9 Comments

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

### 1 comment

**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**

### 5 Comments

Now, first three insertions will not cause a split: 1/2/3

The fourth insertion causes split:

3

1/2 4

Now, the fifth and sixth insertions will not result in a split:

3

1/2 4/5/6

Now, the seventh insertion will create a split:

3/6

1/2 4/5 7

Now, eight and ninth insertions will not create a split:

3/6

1/2 4/5 7/8/9

Now, the tenth insertion causes split :

3/6/9

1/2 4/5 7/8 10

We have 3 splits. But, this is not the maximim number of splits. For max number of split we need insert along the leaves which have the majority elements, shown below by other users. Therefore 3 is not the right answer.