Faygoat's blog

Range Query on a BST
By Faygoat, 11 years ago, In English

So I'm solving a problem that I think requires a binary search tree.

Is it possible to query for the maximum value on a key range? For example, for a node, I have the key be the "time", and the value be some arbitrary number. Is it possible to query for the maximum value where the key is on a range [a, b]? (In logarithmic time).

I googled for range trees and stuff, but those talk about reporting the points on a specified range, which is O(logN + K) where K is the number of points reported. I just want to query for a maximum value (to speed up dynamic programming).

UPDATE: Uh, the points are way too large to actually build a segment tree on it. That's why I'm using a binary search tree. (I already know I can build a seg-tree, but the points are too large, even after compression).

Thanks!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There is some confusion between the terms "Range tree", "Segment Tree" and such. Anyway you are looking for RMQ. There is a good tutorial on topcoder: RMQ with Segment trees

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's possible and straightforward, assuming your BST is balanced and augmented with maximal values for every subtree. You just need to know which range of keys is covered by the given node:

  1. Root node covers all possible keys.
  2. If the node with key m covers [x, y] range, then its left child covers [x, m) and its right child covers (m, y]. (Assuming keys are unique.)

So, start with the root node and consider the following cases:

  1. If the key of the node is inside [a, b], take its value into calculation of the maximum.
  2. If the range covered by the node is completely inside [a, b], you shouldn't traverse its subtrees. Just take its maximal value.
  3. If the range covered by the node has no common keys with [a, b], you shouldn't traverse its subtrees either. Just ignore it.

By the way, BST takes even more memory space than segment tree built over compressed data. If the set of all possible keys is reasonably small and known in advance, there is no much point in using BST.

→ Reply