31 votes

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

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.

- The height of the tree remains the same.
- The node
$K20$ (disregarding the links) is present in the tree.

- The root node remains unchanged (disregarding the links)$1$

Which one of the following options is true ?

- Statements (i) and (ii) are true
- Statements (ii) and (iii) are true
- Statements (iii) and (i) are true
- All the statements are false

32 votes

2

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

40

Shouldn't the final tree should look like below :

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

0

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 ?

0

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

2

@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

0

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

0

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

0

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

0

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

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.

0

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

3

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

10 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**

3

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

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

5 votes

So according to my answer

- Height of Tree is the same
- Node with single $K20$ node is present
- But root changed to $K30$

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

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

3 votes

0 votes

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