# 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.

• 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 '12 at 23:44
• @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 '12 at 21:13