Past exam question: 2062 Baishakh (Regular / Back), Q10
Open in the Padhaiko appQuestion
Write an algorithm for the searching in multiway search tree.
Solution
Structure of an -Way (Multi-Way) Search Tree Node: Each node in an -way search tree (such as a B-Tree) contains:
- sorted keys (): .
- child pointers , where all keys in subtree are , keys in lie between and , and keys in are .
Algorithm MULTIWAY_SEARCH(node, target):
Algorithm MULTIWAY_SEARCH(node, target):
1. If node == NULL:
Return (NULL, -1) // Search failed
2. i = 0
3. While i < node->numKeys and target > node->keys[i]:
i = i + 1
4. If i < node->numKeys and target == node->keys[i]:
Return (node, i) // Found at index i inside node
5. If node->isLeaf:
Return (NULL, -1) // Leaf reached; target absent
6. Return MULTIWAY_SEARCH(node->children[i], target)
Complexity: At each level of height , at most (or with binary search inside the node) comparisons occur, giving search time and node/disk accesses.
Answer:
MULTIWAY_SEARCH scans the sorted keys keys[0..numKeys-1] in the current node to find the first keys[i] >= target: if equal, it returns (node, i); otherwise it descends recursively into children[i] until either matching or reaching a leaf (NULL).