edited by
17,569 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
edited by

5 Answers

Best answer
55 votes
55 votes

Now merge $40$ in upper level.

Now redistribute:

So, the answer is A.

edited by
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
3 votes
3 votes

Answer is A) in both the cases.

Answer:

Related questions

46 votes
46 votes
5 answers
1
53 votes
53 votes
5 answers
4
Ishrat Jahan asked Oct 30, 2014
17,714 views
Consider the following two transactions$: T1$ and $T2.$$\begin{array}{clcl} T1: & \text{read (A);} & T2: & \text{read (B);} \\ & \text{read (B);} & & \text{read (A);} \\ ...