PR Quadtree

A PR (Point Region) Quadtree is a four-way search trie. This means that each node has either four (internal guide node) or zero (leaf node) children. Keys are only stored in the leaf nodes, all internal nodes act as guides towards the keys.

A PR Quadtree follows the following rules:

1. At most, one vertex can lie in a region represented by a quadtree leaf node.
2. Each region's quadtree leaf node is maximal.
3. Internal guide nodes are considered to be "gray" nodes.
4. Leaf nodes that contain data are considered to be "black".
5. Leaf nodes that are empty (they simply exist to fulfill the 4-way property) are considered to be "white".
6. Each gray node must have at least two children that are black and/or one child that is a valid gray node.
7. If, after a deletion, a gray node has three white children and one black one, the gray node must be deleted and replaced by the black child node.

Here is a link to some slides further explaining the PR Quadtree: PRQuadTrees

And a lecture concerning its implementation PRQuadTrees Implementation

Web Accessibility