Difference between revisions of "PR Quadtree"
From CMSC 420
| Line 9: | Line 9: | ||
# Each gray node must have at least two children that are black and/or one child that is a valid gray node. | # Each gray node must have at least two children that are black and/or one child that is a valid gray node. | ||
# 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. | # 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: | ||
| + | [http://courses.cs.vt.edu/~cs3114/Spring10/Notes/T06.PRQuadTrees.pdf PRQuadTrees] | ||
| + | |||
| + | And a lecture concerning its implementation | ||
| + | [http://courses.cs.vt.edu/~cs3114/Spring10/Notes/T07.PRQuadTreeImplementation.pdf PRQuadTrees Implementation] | ||
Latest revision as of 14:24, 7 June 2010
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:
- At most, one vertex can lie in a region represented by a quadtree leaf node.
- Each region's quadtree leaf node is maximal.
- Internal guide nodes are considered to be "gray" nodes.
- Leaf nodes that contain data are considered to be "black".
- Leaf nodes that are empty (they simply exist to fulfill the 4-way property) are considered to be "white".
- Each gray node must have at least two children that are black and/or one child that is a valid gray node.
- 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
