GATE IT 2007 | Question: 84

Question

Consider the $B^+$ tree in the adjoining figure, where each node has at most two keys and three links.

Keys $K15$ and then $K25$ are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Comments

Part 2 of the Question : https://gateoverflow.in/3537/gate2007-it-85

---

Do you have the actual question paper. Can you please share it. Its no where available in the web. Moreover there are many mistakes while copying the questions in websites like solutionsadda, geeksforgeeeks etc. Pls Pls...

---

In Left and Right Biased both will give you only 20,25 node to be present 

Answer 1

Option (A) is correct.

It is a $B^+$ Tree.

After inserting $K15$ we get

 

Now, we insert $K25$, which gives -

So, we see in the final tree only $\text{(K20, K25)}$ is present. Hence, 1 (Ans).

Comments

when u inserted 15..

why have u created seperate node of 15..?

why not u have kept K 15  next to K10...plzz explain...

---

You have used right biasing it could be done by left  or it is stricter requirements to do one type

---

^
If u see the tree carefully then u will observe that they have used right biasing here, otherwise this tree won't be possible.

---

Even if we have take right biasing, don't you think the root node should have the 50. I am trying to apply the concept described in NPTEL video.

https://www.youtube.com/watch?v=aVMSNLnZc-Q&list=PLyvBGMFYV3auVdxQ1-88ivNFpmUEy-U3M&index=25

---

@abhijit, In this nptel lectures, sir has used left biasing. You can visualize the tree using right biasing here. simply insert the value after selecting the proper order of the tree.

B+ tree.

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

B tree.

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

---

Please explain what is the meaning of

(disregarding the links) here??as given in question.

---

Even with left biasing, we will get K20, K25 node only from the given list of nodes. Am I right?

And how is @Sachin sir saying that it is using right biasing? I didn't get his concept.

---

@Rishabh tree itself is formed using right biasing i don't think we should start inserting values using left bias in the half way

---

@Utkarsh ohk. But how to know just by looking at the tree that it's left or right biasing? I have a lot of confusion in B and B+ trees. Nothing much is given in Korth.

---

In 2nd level (20,30) node will be there, not (30,_)

---

can you explain actually what he is asking am not understanding the meaning of disgrading the link here ??

---

Sir/Ma'm Please someone help. What is the number of leaf splits? Is it 2 or 1?

---

@VipulSingh890

What is the number of leaf splits? Is it 2 or 1?

it is 2.

 

@Shubham Aggarwal

the meaning of disgrading the link here

it means don't worry about the pointers to whom they linked !

simply saying, is there any node containing those 2 keys only ?

---

@abhijit no 50 should not be there it should be a minimum of right subtree which is 40, and why a minimum of right subtree it is because right subtree should have keys which are greater than or equal to the key of the root

---

Can u explain what do u mean by left & right biasing as I've searched it on internet but found nothing , so if there is any source to study that????

---

I know the way to insert in b+ tree is that first we're going to insert k15 as the left child of k30 & as it's become more than its Max size it can occupy so shifting middle element i.e, k15 only to.the upper level & when at second time k25 is to be inserted  it'll just inserted to the near by of k20 . Is it wrong???

---

What if we use redistribution policy??

---

I am new to this concept. Here's my attempt.  Can anyone please tell me if this is the right tree structure after insertion

---

For those having doubt, why isnt there a node like [K20,K30] after insertion of 25 as internal node?

Notice that when we split on a internal node, the median search key is propagated only upwards, and is not stored in either of the newly formed nodes after split.

I had this doubt for long, so thought maybe it can save you some time.

Answer 2

Answer: A

Only one node will be there, i.e. (K 20,K 25). After inserting K 15, the node (K 10, K 20) splits and K 15 moves up to form (K 15,K 30).

After K 25 is inserted, K20 moves up to the root  & splits up (K15,K30) &  it forms (K 20,K 25).

So, after final insertion only (K20,K25) present.  So, 1 is the answer.

Comments

i am getting (15,20).... where did you insert 25 ...?

pls explain little bit more ...

---

@Sonam, see the selected answer.

Answer 3

I am not adding complete answer but just adding some useful points

In B+ tree unlike B tree in case of overflow we keep value in leaf as well as promote value to parent node

For intermediate nodes operation is same for both B and B++ i..e promote value to parent node don't keep value in child node

In case of left Biasing : when in case of overflow no of keys are odd , take middle key with left sibling

In case of right Biasing : when in case of overflow no of keys are odd , take middle key with right sibling

follow only one biasing for all splits in tree , dont change method in between.  hence answer is (20,25) in either left biasing or right one.

Comments

@mehul vaidya can you give some reference for left and right biasing because as of now it doesn't seem correct as well as in textbook(Korth) clearly given when right bias and when keys are odd or even then first key(which is smallest from right) taken as a root

Answer 4

Caption

[K20,K25] present. Therefore, option A.

 

Answer 5

1 node will be there (15,20)

Comments

yes man that is the how that algo works. And you are right 25,30 will not be present only 15,20...here is the tree(sorry for formatting :(

                        25,40

      15                30             50

10      15,20    25     30    40     50

when 15 comes first it will split 10,20 into two nodes and 15 itself will go up at middle level(15,30). Now when 25 comes in it will violate the condition of order at the middle level(15,30) and so it will split this node and so 25 will go up at the root level...and rest is in the figure.

---

When 25 comes, wont it be inserted in the leaf to form (20,25). your answer seems different from the accepted answer.

---

it is b tree , u r considering it as b ++ . please check