natural extension of the bst to multiple dimensions it is binary tree whose splitting decisions alternate among the key dimensions like the bstthe - tree uses object space decomposition the pr quadtree uses key space decomposition and so is form of trie it is binary tree only for one-dimensional keys (in which case it is trie with binary alphabetfor dimensions it has branches thusin two dimensionsthe pr quadtree has four branches (hence the name "quadtree")splitting space into four equal-sized quadrants at each branch section briefly mentions two other variations on these data structuresthe bintree and the point quadtree these four structures cover all four combinations of object versus key space decomposition on the one handand multi-level binary versus -way branching on the other section briefly discusses spatial data structures for storing other types of spatial data the - tree the - tree is modification to the bst that allows for efficient processing of multidimensional keys the - tree differs from the bst in that each level of the - tree makes branching decisions based on particular search key associated with that levelcalled the discriminator we define the discriminator at level to be mod for dimensions for exampleassume that we store data organized by xy-coordinates in this casek is (there are two coordinates)with the xcoordinate field arbitrarily designated key and the -coordinate field designated key at each levelthe discriminator alternates between and thusa node at level (the rootwould have in its left subtree only nodes whose values are less than nx (because is search key and mod the right subtree would contain nodes whose values are greater than nx node at level would have in its left subtree only nodes whose values are less than my there is no restriction on the relative values of mx and the values of ' descendantsbecause branching decisions made at are based solely on the coordinate figure shows an example of how collection of two-dimensional points would be stored in - tree in figure the region containing the points is (arbitrarilyrestricted to squareand each internal node splits the search space each split is shown by linevertical for nodes with discriminators and horizontal for nodes with discriminators the root node splits the space into two partsits children further subdivide the space into smaller parts the children' split lines do not cross the root' split line thuseach node in the - tree helps to decompose the space into rectangles that show the extent of where nodes can fall in the various subtrees