Binary search tree with special operations

user_10667754 0
Viewed 51

Assume we have the normal binary search tree over integers.

I am interested in the number of elements that are multiples of 3 and greater than a given number x. Also, I am interested in the number of elements that are multiples of 3 and strictly between two given numbers x1,x2 with x1 < x2. The naive approach would be for example to search the number x and then check each number if it is a multiple of 3. Is there a way to modify the binary search tree, such that these two operations are more efficiently

binary-search-tree binary-tree algorithm
1 Answers

In every node, you can keep a count of the number of multiples of 3 in that node's subtree.

These counts can be maintained without changing the complexities of add/remove/rotate/rebalance operations.

Then to count the number of multiples of 3 greater than x, you search for x. Whenever you go left at a node (because it's > x), you add the count from that node, and subtract the count from the node you move to.

If you find x in an internal node, add the count from its right child.

user_54835260
Related