CODEWITHSUNDEEP
algorithmdata-structurestreered-black-tree
Sarah Grant
Sarah Grant

Reputation: 21

RB tree with sum

I have some questions about augmenting data structures:

Let S = {k1, . . . , kn} be a set of numbers. Design an efficient data structure for S that supports the following two operations:

Insert(S, k) which inserts the number k into S (you can assume that k is not contained in S yet), and TotalGreater(S, a) which returns the sum of all keys ki ∈ S which are larger than a, that is, P ki∈S, ki>a ki .

Argue the running time of both operations and give pseudo-code for TotalGreater(S, a) (do not given pseudo-code for Insert(S, k)).

I don't understand how to do this, I was thinking of adding an extra field to the RB-tree called sum, but then it doesn't work because sometimes I need only the sum of the left nodes and sometimes I need the sum of the right nodes too.

So I was thinking of adding 2 fields called leftSum and rightSum and if the current node is > GivenValue then add the cached value of the sum of the sub nodes to the current sum value.

Can someone please help me with this?

Upvotes: 2

Views: 895

Answers (2)

Theis F. Hinz
Theis F. Hinz

Reputation: 183

As Jordi describes: The key-word could be augmented red-black tree.

Upvotes: 0

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

You can just add a variable size to each node, which is the number of nodes in the subtree rooted at that node. When finding the node with the smallest value that is larger than the value a, two things can happen on the path to that node: you can go left or right. Every time you go left, you add the size of the right child + 1 to the running total. Every time you go right, you do nothing.

There are two conditions for termination. 1) we find a node containing the exact value a, in which case we add the size of its right child to the total. 2) we reach a leaf, in which case we add 1 if it is larger than a, or nothing if it is smaller.

Upvotes: 1

Related Questions