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

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

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

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.