# 2-D Range Tree Demo

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

#### Instructions

Use **Insert** and **Delete** to define a set of points. When
done, select **Window** to create the 2D range tree. In **Window**
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.