The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 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$

+26 votes

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

Is there any condition for that?

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

+4 votes

–1 vote

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.

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, :)

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,846 answers

115,882 comments

39,703 users