Enhance B-Tree with find(k) function

Question

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to be in $O(t \cdot \log_t{n})$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)

for example, for this tree (Only example! max degree = 3, t=2 because $MaxDeg = 2 \cdot t - 1$):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)

I thought about storing how many keys are before each key, and thus we can actually do it in $O(1)$ but it seems unrealistic, if the question asks for $O(t \cdot log_t{n})$

Thank you!

Answer 1

First take the case when you don’t have any key repeated: you can use an ordinary Binary Search Tree (BST) and perform an inorder traversal for searching the required key. Since inorder traversal gives you the keys in sorted order, so you can simply maintain a counter which you increase every time you visit a new node.

Since, you want to allow multiple occurrences of keys, you need need to modify the node to have a integer to hold the number of times that key has been added.

It’s quite easy to fill the details.