Priority Search Tree Demo

A priority search tree is a data structure that allows for efficient searching and point location in one and one-half dimensions (the upper bound on Y is missing). It is a hybrid of a heap and a balanced search tree (heap for y-coordinates, search tree for x-coordinates).

The applet below (my final project for Computational Geometry) demonstrates the data structure and algorithm described by Edward McCreight in his 1985 paper Priority Search Trees. For more information on priority search trees, read the lectures Priority Search Trees (Scribe: Dina Q Goldin Karon) and Dynamic Priority Search Trees (Scribe: Mike Shapiro). There's also a good paper entitled Tutorial on Priority Search Trees by Wen-Chun Ni.

[ How to use this applet | Technical info about this applet ]

</COMMENT> Can't display applet: not a Java browser.

[ Browse pointsets | Submit pointset ]

Michael J. Radwin,

Last modified: Tue Mar 4 09:33:04 EST 1997