2
$\begingroup$

Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges [0], [1], [2], [3], ... , [n], and merging two of them together we end up having the root node holding the range [0, n]. For example we have the following interval tree for an array of size 6.

enter image description here

The total amount of nodes is O(n).

I'm trying to understand what's the maximum posible root - internal node paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of log n but I can't see why, which is the reason why I'm asking this question.

For example in the picture above, for the query [1, 4] we will do the following visits:

[0,5] => [0,2] => [0,1] => [1] => [0,1] => [0,2] => [2] => [0,2] => [0,5] => [3,5] => [3,4] => [3,5] = > [0,5] => end

We have to travel from the root to some other internal node 3 times in total.

Now let's see a different example:

enter image description here

If our query is [1, 8] we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.

So I can't understand why querying in an interval tree is O(log n).

How can you formally prove that querying is indeed O(log n), ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of log n?

$\endgroup$
  • $\begingroup$ You asked a very similar question before. $\endgroup$ – Raphael Nov 16 '14 at 22:47
  • $\begingroup$ I removed that question because it was unclear and very badly written, which led to confusion as to what I was trying to find out. Hopefully that wasn't a bad decision from my side. Now I see that sometimes it's better to study the properties or your problem, what it is that you're trying to find out and then make an asymptotic analysis of your algorithm compared to that. $\endgroup$ – jsguy Nov 17 '14 at 10:58
  • $\begingroup$ I see. No, that's very fair; given the switch from segment to interval tree I thought you were posting the same question for "the next" data structure, hence my confusion. (Note that you can edit to improve a question and request reopening.) $\endgroup$ – Raphael Nov 17 '14 at 11:02
0
$\begingroup$

Querying an interval tree is $O(\log n + m)$, where $n$ is the size of the tree and $m$ is the size of the output. This explains your confusion. Note that there is a trivial $\Omega(m)$ lower bound.

Unfortunately I couldn't find an online proof of this bound, and since there are many variants of interval trees and many different queries, it's best if you tried to prove it yourself for your type of interval tree and query.

$\endgroup$

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.