PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q10

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Question

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:

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).

All past exam questions for Data Structure and Algorithms