[10 points) Let T be a binary search tree with n nodes and height (log n), where

Question

[10 points) Let T be a binary search tree with n nodes and height (log n), where each node z of T stores a r.key value (which is a real number), as well as an augmented value r.sum as introduced above in Problem7 Describe an algorithm QueryPartialSum(T, k1, k2) which answers the following query: Given two ranks k, and k2, return the total sum of all keys in T whose rank falls in [k1,k2]. For example, QueryPartialSum(T, 1,n) should return the sum of all keys stored in T, and QueryPartialSum(T 1.k) returns the sum of smallest k keys stored in T You can only use the current tree structure - but you may augment it if you need to (although there are solutions without needing to do that). Give the time complexity analysis of your algorithm. Slower but correct algorithm will receive partial its.

Explanation / Answer

Here problem 7 is not mentioned so I am assuming I can use the x.sum variable as I like. If you want something to change please comment.

Idea is to store the sum of all the values which are less than x.key in x.sum. So that whenever we want to get the sum of keys two ranks we can subtract x.sum of the first Rank node from x.sum of the second rank node which will give us sum of keys in T whose rank fall in [first rank, second rank].

The ways we can achieve above is by changing the insert_in_BST . When ever we want to inser a key if it's value is less than root's key we increase sum of root and all nodes on right, by that key and go onto left subtree. If the value of the new key is greater than root's key we change value of sum of new key equal to addition of root.sum and root.key .

By using above technique we can create a BST with nodes having key and sum of all keys less than that key.

Now when defining QueryPartialSum we will just have to look at they nodes with given rank and just substract sum variabiable of smaller rank node from bigger rank node.

Time complexity of algorithm will only depend upon finding the node with the given rank will take at most O(logn).

I had to put quite a efforts to come up with the solution, If you like it please rate if you have any confusion please comment.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.