The PR Quadtree

While the treemap with comparator from Part 1 was sufficient to satisfy all queries related to the spatial coordinates of sites whose data had been mapped into the treemap, anecdotal evidence alleges that range searches cannot be done efficiently using such a structure. So, in Part 2, your job will be to implement the spatial database using a PR quadtree, a 4-ary tree organized as a 4-way search trie, where the data values stored in internal nodes are called ``guides'' that are selected to permit quick access to the leaf level. The only leaf node that will be examined will be the one containing (or that should contain) the target data value, called a ``key''.

Warning: The convention of referring to the data values in internal nodes as guides or search guides, and data values in leaf nodes as keys or search keys will be used for the rest of the course.

Unlike the f-heap and the B+ tree, discussed below, there is agreement upon the definition of a PR quadtree. So, for the time being, visit your local reference book. And check out google using ``PR quadtree'' as the search term for a neat honor's thesis.

Web Accessibility