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.