The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

The following key values are inserted into a $B+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The $B+$ - tree is initially empty

$10$, $3$, $6$, $8$, $4$, $2$, $1$

The maximum number of times leaf nodes would get split up as a result of these insertions is

- $2$
- $3$
- $4$
- $5$

+33 votes

Best answer

In this question they have asked only to count leaf node splits.

So after discussing with my friends on fb, I found that you will get two different answers depending on which convention you follow.

Convention 1: put the middle element in the left node, if you follow this you will get $4$ as answer.

Convention 2: put the middle element in the right node, if you follow this you will get $3$ as answer.

$4$ splits

1. after inserting $6$

2. after inserting $4$

3. after inserting $2$ (there will be an internal node split and a leaf node split)

4. after inserting $1$

So after discussing with my friends on fb, I found that you will get two different answers depending on which convention you follow.

Convention 1: put the middle element in the left node, if you follow this you will get $4$ as answer.

Convention 2: put the middle element in the right node, if you follow this you will get $3$ as answer.

$4$ splits

1. after inserting $6$

2. after inserting $4$

3. after inserting $2$ (there will be an internal node split and a leaf node split)

4. after inserting $1$

**MAXIMUM** number of splits which would be achieved only using left biasing B+ tree. So, 4 is the only correct answer.

which order you are following , is it 3 or 2 .

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"

"The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it."

Read this statement from the question carefully. Both have same meaning.

Read this statement from the question carefully. Both have same meaning.

Those you want to visualize the tree. Draw the tree here by simply inserting the value. It will be right biased.

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

+6 votes

i have tried to draw it and getting** "4"** split of leaf node using **"left biasing"**

**correct me if you found any mistakes**

@prateek.. Yes u r correct but can u pl tell me what ans are u getting if we follow right biasing.. Bcz m getting 3..with right biasing also.. Am i correct?

Here, order is 3 so we can take only 2 key values in the internal nodes ,

so there should be split in the node having value 3, 4, 6 as in que --

The maximum number of times leaf nodes would get split up as a result of these insertions is asked

so ans would be 4 only .

so there should be split in the node having value 3, 4, 6 as in que --

The maximum number of times leaf nodes would get split up as a result of these insertions is asked

so ans would be 4 only .

order of the internal nodes is 3 and order of internal nodes is the maximum number of tree pointers in each node

But at step 6, Your internal node has 4 poimters .

kapil plz help in below question...

why the height of the tree will not decrease....???

https://gateoverflow.in/3537/gate2007-it-85

@prateek in ur ans at insert1 there are 2 split 123(at level 3)and 2346 (at level 2)

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain

@prateek

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....

+3 votes

answer is **3** if followed right biasing, means, putting middle element in right node.

and, answer is **4 **if followed left biasing, means, putting middle element in left node.

but actually, which to follow officially ?

however, maximum is asked in this question, so ,there is a reason to choose left biasing here.

+3 votes

*The** maximum number of times leaf nodes would get split up as a result of these insertions is* so the correct ans should be **4 **only

0 votes

0 votes

THANK YOU

Correct me if I am wrong !!

–2 votes

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,230 answers

114,269 comments

38,798 users