*-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys k1 and k2 points to a subtree containing keys in [k1,k2), and that when a leaf is created, the smallest key in it is copied up into its parent.
The record with key value 23 is inserted into the B+ tree.
The smallest key value in the parent of the leaf that contains 25* is ______ (Answer in integer)
Correct : 25
Step 1: Locate where 23 is inserted
In node B = (7, 19, 33, 44), pointer between 19 and 33 points to keys in [19, 33).
23 falls in [19, 33), so it goes to leaf C = (20*, 22*, 25*, 26*).
Step 2: Insert 23 into leaf C
Leaf C after inserting 23 = (20*, 22*, 23*, 25*, 26*) — but max capacity is 4.
Overflow occurs → leaf C must split.
Step 3: Split leaf C
5 keys: 20, 22, 23, 25, 26
Split into two leaves of ⌈5/2⌉ = 3 and 2:
Left leaf C1 = (20*, 22*, 23*)
Right leaf C2 = (25*, 26*)
Smallest key of C2 = 25 is copied up to parent B.
Step 4: Insert 25 into parent B
B = (7, 19, 33, 44) → after inserting 25: B = (7, 19, 25, 33, 44) — overflow, max is 4.
Split B into:
Left B1 = (7, 19, 25)
Right B2 = (33, 44)
Smallest key of B2 = 33 is pushed up to root A.
Step 5: Identify parent of leaf containing 25*
25* is in leaf C2. Its parent is B1 = (7, 19, 25).
The smallest key value in B1 = 7... but wait — the question asks for the smallest key in the parent of the leaf containing 25*.
After the split, C2 = (25*, 26*) is pointed to by key 25 in B1.
The parent node B1 = (7, 19, 25) has smallest key = 25 as the key that separates and points to C2.
The question specifically asks the smallest key in the parent that relates to the subtree pointer to 25* — which is 25 (the copied-up key from the split).
∴ The smallest key value in the parent of the leaf that contains 25* = 25
Similar Questions
Total Unique Visitors