in Databases edited by
17,247 views
47 votes
47 votes

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. Now the key $K50$ is deleted from the $B^+$ tree resulting after the two insertions made earlier. Consider the following statements about the $B^+$ tree resulting after this deletion.

  1. The height of the tree remains the same.
  2. The node 

    (disregarding the links) is present in the tree.

  3. The root node remains unchanged (disregarding the links).

Which one of the following options is true?

  1. Statements (i) and (ii) are true
  2. Statements (ii) and (iii) are true
  3. Statements (iii) and (i) are true
  4. All the statements are false
in Databases edited by
17.2k views

3 Comments

This is 2nd part of the question
here is first part.
https://gateoverflow.in/3536/gate2007-it-84
14
14

thank you sir, I was thinking how the hell on earth 20 goes to root. 
what would be answer if this image tree would be considered.
i think this, 

1
1
How will we know whether to do re-distribution or node merging?
0
0

5 Answers

55 votes
55 votes
Best answer

Now merge $40$ in upper level.

Now redistribute:

So, the answer is A.

edited by

4 Comments

is node 30 satisying right biasing
0
0

Any good resources to learn about B+ deletion? Very confused.

@Pranavpurkar

0
0
3
3
12 votes
12 votes

Answer is (A)

Only (i) and (ii) are correct .

After deleting 50 from the tree we are left with node (20,40) with 40 having no right subtree except 40 itself.Nodes can't be combined because that would overflow the node as they are already half -full or full .So key 40 can be out in node containing 30 .height remains same with 20 at root

edited by

4 Comments

i think answer is all false
3
3
how can u say (ii) is false?
i agree with height can decrease and root node can change
1
1
this question can be solved with 2 ways.

1) NODE MERGING

2)RE-DISTRIBUTION

if we apply node merging..then height will decrease...

and if we apply re-distribution height remains same..

so statement 1 is true if we apply re-distribution

statement 2 is true...as we know 20 will remain present

statement 3 cannot be true in either case

whether it is node merging or re-distribution ROOT NODE will change surely....in both case

so option 1 matches only

and option ALL FALSE is not true becoz statement 2 is always true 20 will remain inside the tree
3
3
Could you please explain a bit more(if possible with diagram)?
0
0
6 votes
6 votes

So according to my answer

  1. Height of Tree is the same
  2. Node with single $K20$  node is present
  3. But root changed to $K30$

So $\text{Option } A$ is right choice


Reference : https://itu.dk/~mogel/SIDD2011/lectures/BTreeExample.pdf Page 12

edited by
3 votes
3 votes

Answer is A) in both the cases.

1 comment

what is left biasing and what is right biasing can u please explain in detail.
0
0
Answer:

Related questions