The Gateway to Computer Science Excellence
+31 votes
4.7k views

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

GATE2007-IT_84

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?

GATE2007-IT_84

  1. $1$
  2. $2$
  3. $3$
  4. $4$
in Databases by Boss (16.3k points)
edited by | 4.7k views
+5

This is the actual question

4 Answers

+47 votes
Best answer

Option (A) is correct.

It is a $B^+$ Tree.

After inserting $K15$ we get -

    a

Now, we insert $K25$ , which gives -

     b

     so, we see in the final tree only $(K20,K25)$ is present. Hence, 1 (Ans).

by Boss (15.7k points)
edited by
0
when u inserted 15..

why have u created seperate node of 15..?

why not u have kept K 15  next to K10...plzz explain...
0
You have used right biasing it could be done by left  or it is stricter requirements to do one type
+16

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

0

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.

+4

@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

0
Please explain what is the meaning of

(disregarding the links) here??as given in question.
0
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.
+1
@Rishabh tree itself is formed using right biasing i don't think we should start inserting values using left bias in the half way
0
@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.
0
In 2nd level (20,30) node will be there, not (30,_)
0
can you explain actually what he is asking am not understanding the meaning of disgrading the link here ??
0
Sir/Ma'm Please someone help. What is the number of leaf splits? Is it 2 or 1?
0

@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 ?

0

@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

0
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????
0

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

0
What if we use redistribution policy??
+11 votes
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.
by Boss (33.8k points)
0
i am getting (15,20).... where did you insert 25 ...?

pls explain little bit more ...
0
@Sonam, see the selected answer.
+1 vote
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.
by Active (4.9k points)
0

@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

–3 votes
1 node will be there (15,20)
by Loyal (6.9k points)
edited by
+4

Only 1 node will be there . (20,25) only

0
I am following the cormen Btree algo...the way they have done it is try to insert from top and if you find any node violating the Order of tree(here it is 3) then split the node(no key distribution)...just take a look at cormen algo you will get it.
0

@ Marv: I was first looking for  leaf node to insert which I guess is always true. After that if  a leaf node(in which I am inserting is full) we split the node moving the middle key up inserting it in the parent node which may again cause the split.

But I guess Cormen says that we must cause a split while moving DOWN the tree whenever we find  a FULL node rather than causing split after a key has been inserted which was full.

So what I concluded is Split a node that u find full while traversing down the tree starting from root AND DON'T wait to find the right node to insert.

Am I correct to say that ??

If not please hint me on what I wrong at.

Thank You for mentioning .

+1
The question says B Tree.

But ,to me ,It does not seem to be a B Tree.       See every leaf node key is present in the internal node as well and the tree is RIGHT Biased. This seems a B+ Tree instead.

please confirm because answer will vary dramatically in that case !!
+3
@Marv :could you please put up a picture for that solution please.

I am still getting 1 node (20,25)
+1
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.
0
When 25 comes, wont it be inserted in the leaf to form (20,25). your answer seems different from the accepted answer.
0
it is b tree , u r considering it as b ++ . please check

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,578 answers
195,772 comments
101,772 users