chap advanced tree structures nw se ne sw ( , ( , ( ( , ( , ( ( (bfigure example of pr quadtree (aa map of data points we define the region to be square with origin at the upper-left-hand corner and sides of length (bthe pr quadtree for the points in ( (aalso shows the block decomposition imposed by the pr quadtree for this region inserting record into the pr quadtree is performed by first locating the leaf node that contains the location of if this leaf node is emptythen is stored at this leaf if the leaf already contains (or record with ' coordinates)then duplicate record should be reported if the leaf node already contains another recordthen the node must be repeatedly decomposed until the existing record and fall into different leaf nodes figure shows an example of such an insertion deleting record is performed by first locating the node of the pr quadtree that contains node is then changed to be empty the next step is to look at ' three siblings and its siblings must be merged together to form single node if only one point is contained among them this merging process continues until some level is reached at which at least two points are contained in the subtrees represented by node and its siblings for exampleif point is to be deleted from the pr quadtree representing figure ( )the resulting node must be merged with its siblingsand that larger node again merged with its siblings to restore the pr quadtree to the decomposition of figure (aregion search is easily performed with the pr quadtree to locate all points within radius of query point qbegin at the root if the root is an empty leaf nodethen no data points are found if the root is leaf containing data recordthen the location of the data point is examined to determine if it falls within the circle if the root is an internal nodethen the process is performed recursivelybut only on those subtrees containing some part of the search circle