3
$\begingroup$

If we consider the following problem: Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point, and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.

$\endgroup$
  • 1
    $\begingroup$ Are you interested in the amortized complexity? Did they tell you if they want the total cost, was it clear whether the cost of building the data structure had to be included? In either case, the answer to the question your posing is in the link you have included. I am guessing there was some space limitation you forgot to add or some other extra parameter? $\endgroup$ – Konstantinos Koiliaris Jul 9 '15 at 20:50
  • $\begingroup$ No, that link doesn't give the lookup complexity for ALL intervals intersecting a given point for the augmented version of the interval tree. $\endgroup$ – user1715122 Jul 10 '15 at 2:53
2
+50
$\begingroup$

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$. Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

Illustrated example:
interval tree Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$). All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored. However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time. Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time. Because we prune a tree-walk we also have an upper bound of $O(n)$ time. This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But if m=n, then this will give a lookup complexity of O(n log n), which cannot be the case since tree traversal is O(n) $\endgroup$ – user1715122 Jul 15 '15 at 19:24
  • $\begingroup$ Could you elaborate on the answer you have posted? Specifically, the part related to "at most one downward path.." and how that translates to O(min(n,(m+1)logn))? $\endgroup$ – user1715122 Jul 15 '15 at 22:46
  • $\begingroup$ @user1715122: I updated my answer. $\endgroup$ – Tim Jul 17 '15 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.