4
edits
Changes
From CMSC 420
no edit summary
A PR (Point Region) Quadtree is a four-way search trie.
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:
A PR Quadtree follows the following rules:
# At most, one vertex can lie in a region represented by a quadtree leaf node.
# At most, one vertex can lie in a region represented by a quadtree leaf node.
# Each region's quadtree leaf node is maximal.
# 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.
