Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node containing key $x$, or reports that $x$ is not contained in $T$.

Normally, we start a query from the root of a binary search tree, but we don't have to. From any node in the search tree, we can traverse the tree to find the location of any key in the search tree using only local information stored at each node. This takes $O(h)$ time, where $h$ is the height of the tree.

Now suppose we want to support that same $\mbox{Find()}$ query over keys drawn from a partial order. A quadtree built over 2d points has these three interesting properties:

  1. The data in the tree is partially ordered.
  2. We can perform a $\mbox{Find()}$ query in $O(h)$ time using only local information at each node.
  3. It is often used to answer more complex queries.

Question: are there other tree data structures that meet these three criteria?

Justification of the three criteria for the quadtree is included below:

1) Points in two dimensions are partially ordered. Sorting 2d points, or finding the successor of a point $(x,y)$ doesn't have meaning unless we first define a total order on the points, essentially projecting them down to one dimension. (Sort these points lexographically, find the successor of $(x,y)$ along this space-filling curve).

2) Each cell of a quadtree stores an axis-aligned rectangle, and the rectangle of a parent is the union of the rectangles of the children. We can navigate to the correct node in $O(h)$ time by comparing the point we are searching for with the rectangle stored at each node along our search path.

3) e.g. Approximate nearest neighbor or approximate range queries.


Interval trees store partially ordered data (intervals) and can answer complex queries (e.g. find all the intervals overlapping given one/containing given one/etc). Looks like criteria (2) and (3) are met, but I'm not sure if I understand (1) correctly.

  • $\begingroup$ intervals are partially ordered, so (1) is met. (3) is met-- as you point out, interval trees can answer complex queries. Criteria (2) is trickier: We can locate where a particular interval is stored in the interval tree, but since one node could contain up to a linear number of intervals, can we find it in $O(h)$ time? $\endgroup$ – Joe Mar 6 '12 at 23:44
  • $\begingroup$ Yes. you can search for an interval in h time. en.wikipedia.org/wiki/Interval_tree $\endgroup$ – Suresh Venkat Mar 7 '12 at 4:37
  • $\begingroup$ @SureshVenkat I know that we can find a single overlapping interval in $O(h)$ time. My concern is that if most of the intervals are overlapping, could $h$ be $o(\log n)$ while the number of intervals stored in a particular node is $\Omega(n)$? For example, if we have $n$ duplicate intervals, our tree is just one node storing all the intervals, so $h$ is $O(1)$. I think this may also be possible with unique intervals, as long as every interval contains the center point. $\endgroup$ – Joe Mar 7 '12 at 21:13
  • $\begingroup$ the overall run time is log n + k, where k is the output size. But if you want all answers, I'm not sure how you can avoid spending that much time $\endgroup$ – Suresh Venkat Mar 7 '12 at 21:23
  • $\begingroup$ @SureshVenkat I don't want all the overlapping intervals. I want a pointer to a particular interval. Find(I) should return a pointer to interval I, not all intervals overlapping I. If a lot of intervals overlap I, it may be difficult to find I. $\endgroup$ – Joe Mar 7 '12 at 21:32

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.