Statement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node. Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.

Category: QuestionsStatement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node. Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.
Editor">Editor Staff asked 1 month ago

Statement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node.
 
Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.
 
(a) Statement 1 is true but statement 2 is false
 
(b) Statement 2 is true but statement 1 is false
 
(c) Both the statements are true
 
(d) Both the statements are false
 
I’d like to ask this question from B-Trees in section B-Trees of Data Structures & Algorithms I
 
The question was posed to me by my college director while I was bunking the class.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct choice is (a) Statement 1 is true but statement 2 is false
 
Easy explanation – During the split, the middle key is retained in the right half node and also promoted to parent node. When a key is deleted from the leaf, it is retained in non-leaves, because it can be still a valid separator between keys in nodes below.