GATE CS 2021 Set 1 Q.57 (CS Q.47): File Organization, B-Trees and B+ Trees Indexing

Consider a dynamic hashing approach for 4-bit integer keys:

There is a main hash table of size 4.
The 2 least significant bits of a key is used to index into the main hash table.
Initially, the main hash table entries are empty.
Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

5, 9, 4, 13, 10, 7

9, 5, 10, 6, 7, 1

10, 9, 6, 7, 5, 13

9, 5, 13, 6, 10, 14

Official answer and solution

Note on this question

Official key designates this question as MSQ with single correct option C.

Solution

Trace binary representations of candidate insertion sequences to match hash bucket index and internal binary tree split levels.

Write the 4-bit binary representations for keys in candidate sequence C (10, 9, 6, 7, 5, 13):

$10 = 1010_2$ : 2 LSBs are $10_2$ . Goes to bucket 10.
$9 = 1001_2$ : 2 LSBs are $01_2$ . Goes to bucket 01.
$6 = 0110_2$ : 2 LSBs are $10_2$ . Collides with 10 in bucket 10. The 3rd LSB of 10 is 0 and of 6 is 1. Bucket 10 splits into left (0) containing 10 and right (1) containing 6.
$7 = 0111_2$ : 2 LSBs are $11_2$ . Goes to bucket 11 (no collision).
$5 = 0101_2$ : 2 LSBs are $01_2$ . Collides with 9 in bucket 01. The 3rd LSB of 9 is 0 and of 5 is 1. Bucket 01 splits at 3rd LSB into left (0) containing 9 and right (1) containing 5.
$13 = 1101_2$ : 2 LSBs are $01_2$ . 3rd LSB of 13 is 1, which collides with 5 (3rd LSB is 1). Therefore, the right child of bucket 01 splits based on the 4th LSB: 4th LSB of 5 is 0, and 4th LSB of 13 is 1.

This produces exactly the tree structure depicted in the problem figure:

Bucket 00: empty
Bucket 01: root split on 3rd LSB, with left child holding key 9, and right child split on 4th LSB holding keys 5 and 13
Bucket 10: root split on 3rd LSB holding keys 10 and 6
Bucket 11: single key 7 without any splits

Hence, insertion sequence C produces the given hash table state.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.