whose result is shown in figure (bthe second is zigzag rotationwhose result is shown in figure (cthe final step is single rotation resulting in the tree of figure (dnotice that the splaying process has made the tree shallower spatial data structures all of the search trees discussed so far -bstsavl treessplay trees - treesb-treesand tries -are designed for searching on one-dimensional key typical example is an integer keywhose one-dimensional range can be visualized as number line these various tree structures can be viewed as dividing this onedimensional number line into pieces some databases require support for multiple keys in other wordsrecords can be searched for using any one of several key fieldssuch as name or id number typicallyeach such key has its own one-dimensional indexand any given search query searches one of these independent indices as appropriate multidimensional search key presents rather different concept imagine that we have database of city recordswhere each city has name and an xycoordinate bst or splay tree provides good performance for searches on city namewhich is one-dimensional key separate bsts could be used to index the xand -coordinates this would allow us to insert and delete citiesand locate them by name or by one coordinate howeversearch on one of the two coordinates is not natural way to view search in two-dimensional space another option is to combine the xy-coordinates into single keysay by concatenating the two coordinatesand index cities by the resulting key in bst that would allow search by coordinatebut would not allow for efficient two-dimensional range queries such as searching for all cities within given distance of specified point the problem is that the bst only works well for one-dimensional keyswhile coordinate is two-dimensional key where neither dimension is more important than the other multidimensional range queries are the defining feature of spatial application because coordinate gives position in spaceit is called spatial attribute to implement spatial applications efficiently requires the use of spatial data structures spatial data structures store data objects organized by position and are an important class of data structures used in geographic information systemscomputer graphicsroboticsand many other fields this section presents two spatial data structures for storing point data in two or more dimensions they are the - tree and the pr quadtree the - tree is