new leaf node if the node is full nodeit replaces itself with subtree this is an example of the composite design patterndiscussed in section other point data structures the differences between the - tree and the pr quadtree illustrate many of the design choices encountered when creating spatial data structures the - tree provides an object space decomposition of the regionwhile the pr quadtree provides key space decomposition (thusit is triethe - tree stores records at all nodeswhile the pr quadtree stores records only at the leaf nodes finallythe two trees have different structures the - tree is binary treewhile the pr quadtree is full tree with branches (in the two-dimensional case consider the extension of this concept to three dimensions - tree for three dimensions would alternate the discriminator through the xyand dimensions the three-dimensional equivalent of the pr quadtree would be tree with or eight branches such tree is called an octree we can also devise binary trie based on key space decomposition in each dimensionor quadtree that uses the two-dimensional equivalent to an object space decomposition the bintree is binary trie that uses keyspace decomposition and alternates discriminators at each level in manner similar to the - tree the bintree for the points of figure is shown in figure alternativelywe can use four-way decomposition of space centered on the data points the tree resulting from such decomposition is called point quadtree the point quadtree for the data points of figure is shown in figure other spatial data structures this section has barely scratched the surface of the field of spatial data structures by now dozens of distinct spatial data structures have been inventedmany with variations and alternate implementations spatial data structures exist for storing many forms of spatial data other than points the most important distinctions between are the tree structure (binary or notregular decompositions or notand the decomposition rule used to decide when the data contained within region is so complex that the region must be subdivided perhaps the best known spatial data structure is the "region quadtreefor storing images where the pixel values tend to be blockysuch as map of the countries of the world the region quadtree uses four-way regular decomposition scheme similar to the pr quadtree the decompostion rule is simply to divide any node containing pixels of more than one color or value