Priority Search Tree Demo

A structure for storing two-dimensional point data to facilitate semi-infinite range queries of the form (Bx:Ex,By:infinity). It is a range tree in the x coordinate value and a heap in the y coordinate value. Each nonleaf node contains the midrange value of the x coordinate values in its leaf nodes. It also contains a pointer to the point in its subtree with the maximum y coordinate value. For more details, see pages 19-27 and 439-443 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 83-85 and 171-174 of Samet, Design and Analysis of Spatial Data Structures.


Using Insert and Delete to define a set of points. When done, select Search to create the priority search tree. In Search mode click and drag to specify a rectangle. If the rectangle defines a 2D interval [BX:EX],[BY:EY], then all points with coordinates from interval [BX:EX],[BY:+infinity] will be found and displayed.