<p><a href="http://en.wikipedia.org/wiki/Interval_tree" rel="nofollow">Interval trees</a> 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.</p>

CC BY-SA 3.0
2012-03-06T23:44:06.493Z
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
CC BY-SA 3.0
2012-03-07T04:37:44.590Z
Yes. you can search for an interval in h time. http://en.wikipedia.org/wiki/Interval_tree
Suresh Venkat
CC BY-SA 3.0
2012-03-07T21:13:59.057Z
@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
CC BY-SA 3.0
2012-03-07T21:23:48.480Z
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
Suresh Venkat
CC BY-SA 3.0
2012-03-07T21:32:47.003Z
@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
CC BY-SA 3.0
2012-03-08T12:57:10.993Z
@Joe You can order intervals lexicographically (not only by x) so it will be just BST. Find(I) is trivial in $O(h)$ then. No need to look at other intervals while searching for I...
Dmytro Korduban
CC BY-SA 3.0
2012-03-08T19:42:52.700Z
@DmytroKorduban Up to now, I wasn't even considering intervals in 2d, just intervals on the real line. Ordering lexographically doesn't avoid the issue. Perhaps I need to redefine $h$ to also include the height of required auxiliary structures, not just the height of the original tree. Then, by storing the intervals in a BST not just a sorted list, and counting the height of the BST as part of the height of the tree, it does meet my requirements.
Joe
CC BY-SA 3.0
2012-03-06T23:21:11.420Z
2012-03-06T23:21:11.420Z
Dmytro Korduban
<p>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$.</p>

<p>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.</p>

<p>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:</p>

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

<p><strong>Question: are there other tree data structures that meet these three criteria?</strong></p>

<p>Justification of the three criteria for the quadtree is included below:</p>

<p>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 <em>lexographically</em>, find the successor of $(x,y)$ <em>along this space-filling curve</em>).</p>

<p>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.</p>

<p>3) e.g. Approximate nearest neighbor or approximate range queries. </p>

<ds.data-structures><tree>
Trees that structure partially ordered data
Joe
# Trees that structure partially ordered data

(Asked by: username_0 on 2012-03-06)

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.

**Tags:** ds.data-structures, tree

---

## 1 answers

### Answer by username_1 on 2012-03-06. Score: 1

[Interval trees](http://en.wikipedia.org/wiki/Interval_tree) 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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: Yes. you can search for an interval in h time. http://en.wikipedia.org/wiki/Interval_tree  
> **username_0**: @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.  
> **username_2**: 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  
> **username_0**: @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.  
> **username_1**: @Joe You can order intervals lexicographically (not only by x) so it will be just BST. Find(I) is trivial in $O(h)$ then. No need to look at other intervals while searching for I...  
> **username_0**: @DmytroKorduban Up to now, I wasn't even considering intervals in 2d, just intervals on the real line. Ordering lexographically doesn't avoid the issue. Perhaps I need to redefine $h$ to also include the height of required auxiliary structures, not just the height of the original tree. Then, by storing the intervals in a BST not just a sorted list, and counting the height of the BST as part of the height of the tree, it does meet my requirements.  

---

