# Trees that structure partially ordered data

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.

• 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?
– Joe
Mar 6, 2012 at 23:44
• Yes. you can search for an interval in h time. en.wikipedia.org/wiki/Interval_tree Mar 7, 2012 at 4:37
• @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.
– Joe
Mar 7, 2012 at 21:13
• 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 Mar 7, 2012 at 21:23
• @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.
– Joe
Mar 7, 2012 at 21:32