return a key of a node with maximum value within a range of keys in B+ tree

Question

I've been asked a question about B+ Tree.

The question is: Suppose we have object of the following type:

class Obj { private: int value; int key; public: Obj(int uniq_key , int value) }

and I am creating a Generic B+ tree which will sort objects in it leafs nodes by keys and not by values. (The keys are unique values aren't) Now I want to return the key of a node containes Maximum value within a range of keys. For Example:

If I have the following objects inserted in my B+ tree:

Obj a(1,10) , Obj(2,5) , Obj(3,0)

Then by calling this method I will get a return value : 1

I thought of having an extra rank tree with the same data stored in it and a pointer from a leaf node in the B+ tree to it's equivalent node in the rank tree but I think that there is a solution involves adding extra data in the nodes in the B+ tree which can solve this issue.

p.s. I don't know if this post is duplicated - I couldn't find anything else answering this kind of question.

Thank you, Michael

Answer 1

Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants). You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't need to look at its grandchildren etc.).

Now any range can be expressed as the union of $O(\log n)$ subtrees. In other words, you can find $O(\log n)$ nodes such that their descendants cover the range exactly. So, the max value of any node within that range can be obtained by looking at the values in those nodes, and taking the max of them. In this way each query can be answered in $O(\log n)$ time.