Now the key K50 is deleted from the B-tree resulting after the two insertions…
2007
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.
(i) The height of the tree remains the same.
(ii) The node
(disregarding the links) is present in the tree.
(iii) 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.
Attempted by 122 students.
Show answer & explanation
Correct answer: A
Answer: Statements (i) and (ii) are true.
Explanation:
Height remains the same: Deleting the specified key does not cause any node to drop below the minimum required number of keys, so no merges or root removals occur that would reduce the tree height. Therefore the tree’s height is unchanged.
The node (disregarding links) is present: After deletion the physical node that contained the key still exists in the tree (it may simply contain one fewer key). Interpreting “node (disregarding the links)” as the physical node and its remaining keys, that node remains part of the tree.
Root does not necessarily remain unchanged: Deleting a key can require replacing an internal key with its predecessor or successor or otherwise adjusting keys in ancestor nodes. Such key-content changes mean the root’s keys can change even when the tree height does not, so you cannot assume the root remains unchanged.
Conclusion: The first two statements are true and the third statement is false.