sec spatial data structures ( (bfigure pr quadtree insertion example (athe initial pr quadtree containing two data points (bthe result of inserting point the block containing must be decomposed into four sub-blocks points and would still be in the same block if only one subdivision takes placeso second decomposition is required to separate them let us now consider how structure of the pr quadtree affects the design of its node representation the pr quadtree is actually trie (as defined in section decomposition takes place at the mid-points for internal nodesregardless of where the data points actually fall the placement of the data points does determine whether decomposition for node takes placebut not where the decomposition for the node takes place internal nodes of the pr quadtree are quite different from leaf nodesin that internal nodes have children (leaf nodes do notand leaf nodes have data fields (internal nodes do notthusit is likely to be beneficial to represent internal nodes differently from leaf nodes finallythere is the fact that approximately half of the leaf nodes will contain no data field another issue to consider ishow does routine traversing the pr quadtree get the coordinates for the square represented by the current pr quadtree nodeone possibility is to store with each node its spatial description (such as upper-left corner and widthhoweverthis will take lot of space -perhaps as much as the space needed for the data recordsdepending on what information is being stored another possibility is to pass in the coordinates when the recursive call is made for exampleconsider the search process initiallythe search visits the root node of the treewhich has origin at ( )and whose width is the full size of the space being covered when the appropriate child is visitedit is simple matter for the search routine to determine the origin for the childand the width of the square is simply half that of the parent not only does passing in the size and position infor