The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 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?

- $3$
- $4$
- $5$
- $6$

+40 votes

Best answer

+1

Can the answer be different if the elements were different?? How can we prove that the result will hold true for any possible series?

+6

anchitjindal07

question asking for "maximum number of node splitting operations" so we think in worst case

worst case will when we insert elements into same side always

question asking for "maximum number of node splitting operations" so we think in worst case

worst case will when we insert elements into same side always

0

Someone please provide me link to understand insertions and deletions in B and B+ tree properly. I am facing difficulties in this exact topic.

+17 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

+8 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

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

0

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

+4 votes

0 votes

+2

Consider the sequence 1 to 10 for insertion. Since the order is 4, the max number of keys would be 3 and min number of keys would be 1.

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.

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.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 571
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,115 questions

53,224 answers

184,675 comments

70,472 users