2

I'm looking to guava TreeRangeMap that seem to very well suit my needs for a project. The java docs says that is based on a (java standard ?) TreeMap that have O(log(n)) time for get, put and next.

But the TreeRangeMap should be some kind of range tree implementation that according to this SO question have O(k + log(n)) time complexity for queries, O(n) space, with k being the range size?. Can somebody confirm this?

I'm also very interested in the time complexity of TreeRangeMap.subRangeMap() operation. Does it have the same O(k + log(n))?

Thanks.

Community
  • 1
  • 1
dcernahoschi
  • 14,968
  • 5
  • 37
  • 59
  • He does not seem to state what algorithm he uses, but I can imagine, it is actually a [B+ tree](http://en.wikipedia.org/wiki/B+_tree) which is a standard database storage datastructure to support range queries. – Domi Nov 29 '13 at 08:19
  • The `subRangeMap` operation sends a query and creates a new map, so if your range contains k values, you probably end up with the complexity of one range query + k insertions. – Domi Nov 29 '13 at 08:20

2 Answers2

10

It's a view, not an actual mutation or anything. subRangeMap returns in O(1) time, and the RangeMap it returns has O(log n) additive cost for each of its query operations -- that is, all of its operations still take O(log n), just with a higher constant factor.

Source: I'm "the guy who implemented it."

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • Thanks Louis :) I've realized in fact I'm interested in all the values from this subrange that is the complexity of `asMapOfRanges()` method that returns a `Map, V>`. Or is there another way to get all the values from a `RangeMap`? – dcernahoschi Nov 29 '13 at 17:17
  • `asMapOfRanges()` is a view, returning in O(1) time, and iterating over its values is O(n). Iterating over `asMapOfRanges` for a `subRangeMap` probably will, in fact, be `O(log n + k)`. – Louis Wasserman Nov 29 '13 at 18:52
  • @LouisWasserman I know this is old and you are not on that team anymore, but it will be good to have these complexities documented in the javadoc rather than having to look them up in Stackoverflow, thanks – Bozho Dec 25 '20 at 20:49
1

We generally use Range tree to find the points that lie in a given interval [x1, x2] and x1 < x2. However, if the range tree is a balanced-binary tree(as in the case of TreeMap which is implemented with Red-Black tree), the search paths to x1(or successor) and x2(or predecessor) have cost O(log n). When we find them, if there k number of points lie in this range, we will have to report it using Tree traversal which will have linear cost O(k). So in total O(k + log(n)).

I'm also very interested in the time complexity of TreeRangeMap.subRangeMap() operation. Does it have the same O(k + log(n))?

<K,V> subRangeMap(Range<K> subRange) Returns a view of the part of this range map that intersects with range, resulting in just another balanced-binary search Tree. So why not?

Sage
  • 15,290
  • 3
  • 33
  • 38