Register

GATE IT 2007 | Question: 85

• edited by
34,902 views
61 61 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

5 Answers

Best answer
72 72 votes

Now merge $40$ in upper level.

Now redistribute:

So, the answer is A.

• edited by
12 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
6 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
1 flag:
✌ Low quality (Heigenberg “Where is 20 in root node after intersting 15 and 25 220 must be present as anchor key in root”)
0 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

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2007 | Quest...Next → · GATE IT 2006 | Quest...
← Previous in category · GATE IT 2007 | Quest...Next in category → · GATE IT 2006 | Quest...
Position:
Show:

Related questions

67 67 votes
5 answers 5 answers
25.1k
25.1k views
Ishrat Jahan asked Oct 30, 2014
25,102 views
GATE IT 2007 | Question: 84
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....
88 88 votes
5 answers 5 answers
21.9k
21.9k views
Ishrat Jahan asked Oct 30, 2014
21,867 views
GATE IT 2007 | Question: 68
Consider the following relation schemas :b-Schema = (b-name, b-city, assets)a-Schema = (a-num, b-name, bal)d-Schema = (c-name, a-number)Let branch, account and depositor ...
59 59 votes
9 answers 9 answers
22.6k
22.6k views
Ishrat Jahan asked Oct 30, 2014
22,569 views
GATE IT 2007 | Question: 67
Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct.if $A \rightarrow \rightarrow B$ and ...
72 72 votes
8 answers 8 answers
28.5k
28.5k views
Ishrat Jahan asked Oct 30, 2014
28,489 views
GATE IT 2007 | Question: 66
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);} \\ ...