A range tree for two-dimensional point data where the top level structure
is a range tree on the * x * coordinate value where each non leaf
node also contains a range tree on the * y * coordinate values
of all the points in its subtree.
For more
details, see pages 14-19 of Samet,
*Foundations of Multidimensional and Metric Data Structures*
or, see pages 80-83 of
Samet,
*Design and Analysis of Spatial Data Structures*.

Use **Insert** and **Delete** to define a set of points. When
done, select **Search** to create the 2D range tree. In **Search**
mode click and drag to specify a rectangle. All points in this rectangle
will be located and displayed.

The animation shows the algorithm's execution. The vertical black
lines correspond to the midrange * x * coordinate values stored
in the nonleaf nodes of the tree. Up to four partition levels are
shown with the depth of the partition to the immediate left of the
vertical line.
The thickness of the vertical lines varies with the thickest lines
corresponding to the shallowest partition level.

The orange lines show the traversal of the linked list stored in leaves
of the 1-d range tree rooted in the current node on the above mentioned
path. The length of the orange lines indicates the maximum possible range
of *x* coordinates of nodes stored in that 1-d range tree.