GATE IT 2007 | Question: 85

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

• A. Statements (i) and (ii) are true
• B. Statements (ii) and (iii) are true
• C. Statements (iii) and (i) are true
• D. All the statements are false

Comments

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

---

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, 

---

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

Answer 1

Now merge $40$ in upper level.

Now redistribute:

So, the answer is A.

Comments

little mistake in ptr of (30,40) node but doesn't affect the ans.

---

how you made that tree by insertion plz explain???

---

The tree in the question and the tree with you started are different. ? How you got the new tree.

---

actually this  is the 2nd part of a qs, in the ist part 15 and 25 were inserted and after that deletion of 50 takes place that is why

---

@srestha please explain redistribution?

---

what the second point means "disregarding the links"?

---

Hi

Can you please tell what is the problem with this diagram? Is it violating any rules?

---

Shouldn't the final tree should look like below :

considering that the given B+ tree in the question is right biased.

---

@Ayush your tree is correct!

---

@Ayush Upadhyaya

I have one doubt why can't we merge k30,k40 in a single node in last level ?

and then 2nd last level would have 2 nodes ,one with K15 and one K30 ?

---

@VS-Okay, if I follow your advice, then in that would the tree remain right biased?

---

@Ayush Upadhyaya

Yes, we merged the last two nodes i.e. we merge k30,k40 in a single node in last level

and k30 is present in internal nodes as well and no need to accommodate k40 in internal nodes

---

@Ayush.Your tree is correct.

B+Tree Property :- Number of Keys in the internal Nodes=Number of leaf nodes -1 and this property is not followed in the given Answer.But yours is correct.

@Vs:- There is a specific algorithm to perform deletion on these tree. YOu can refer:http://www.geeksforgeeks.org/b-tree-set-3delete/ :- Both b and b+tree follow almost same deletion procedure

---

IT IS RIGHT BIASED NA..how 30 & 40 in d same node at the last level???

---

Why to redistribute? Even others node have a single key. We either borrow or re distribute in case particular node doesnt  satisfy minimum number of  key criteria

---

Can anyone please explain why after deletion redistribution has to be done. And how this redistribution has happened.

---

#rahul "B+Tree Property :- Number of Keys in the internal Nodes=Number of leaf nodes -1"  is tha a correct statement ?? as i cant see that property is holding ....

---

@abhijit

It violates the property of B+ tree that an internal node should have atleast ceil[p/2] children where"p" is the order of internal node i.e the max. no. of childrens an internal node can have.

---

ayush upadhayay tree is right

---

Anyone Please explain redistribution.

---

30 Should be on the left of root 40.

---

it is right biased according to the figure in the question since the keys in the right child are greater then equal to the parent

---

@Ayush Upadhyaya   @Shaik Masthan @Arjun

Pls I am not understanding how the redistribution (after 40 is moved to upper level ) is done either in the selected answer or your answer.. (@Ayush)

and what are the different ways of merging in right and left biased B+ trees respectively...

It would be very kind if you provide a good source to study about redistribution.

---

is node 30 satisying right biasing

---

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

@Pranavpurkar

---

Abhrajyoti00

explained clearly here

https://youtu.be/JZhdUb5F7oY?t=1967

after the video refer this.

https://www.javatpoint.com/b-plus-tree-deletion

 

Answer 2

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

Comments

i think answer is all false

---

how can u say (ii) is false?
i agree with height can decrease and root node can change

---

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

---

Could you please explain a bit more(if possible with diagram)?

Answer 3

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

Answer 4

Answer is A) in both the cases.

Comments

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