0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you!!! So if I understand your solution correctly , I am doing twice Find(x) method which will give me the nodes which has the minimum key and maximum key in the given edge. Then I will go back to the parent of each node (parent_left and parent_right) the number of nodes between those two nodes (parent_left and parent_right) is O(logn). And finally I will do linear search within this range of nodes which will be in O(n) time and return the maximum value. so this algorithm will be O(n) and not O(logn) - what did I got wrong in your algorithm? $\endgroup$ – ms_stud Jan 2 '18 at 15:42
  • $\begingroup$ @ms_stud, no, that doesn't sound like what I had in mind. I don't quite understand what you are suggesting but it doesn't seem to be what I had in mind. A first step for you: See if you can figure out why any consecutive range of leaves can be covered by a disjoint union of $O(\log n)$ subtrees. $\endgroup$ – D.W. Jan 2 '18 at 16:00
  • $\begingroup$ Ok. Probably I didn't quite understand your solution. Can you provide me an example? thank you $\endgroup$ – ms_stud Jan 2 '18 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.