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:
- The data in the tree is partially ordered.
- We can perform a $\mbox{Find()}$ query in $O(h)$ time using only local information at each node.
- 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.
