Java Reference
In-Depth Information
C
A
A
B
B
(A)
(B)
Figure13.17
PR quadtree insertion example. (a) The initial PR quadtree con-
taining two data points. (b) The result of inserting point C. The block containing A
must be decomposed into four sub-blocks. Points A and C would still be in the
same block if only one subdivision takes place, so a second decomposition is re-
quired to separate them.
whose y value falls in the range 0 to 63. If the root's child is a leaf node, then that
child is checked to see if Q has been found. If the child is another internal node, the
search process continues through the tree until a leaf node is found. If this leaf node
stores a record whose position matches Q then the query is successful; otherwise Q
is not in the tree.
Inserting record P into the PR quadtree is performed by first locating the leaf
node that contains the location of P. If this leaf node is empty, then P is stored
at this leaf. If the leaf already contains P (or a record with P's coordinates), then
a duplicate record should be reported. If the leaf node already contains another
record, then the node must be repeatedly decomposed until the existing record and
P fall into different leaf nodes. Figure 13.17 shows an example of such an insertion.
Deleting a record P is performed by first locating the node N of the PR quadtree
that contains P. Node N is then changed to be empty. The next step is to look at N's
three siblings. N and its siblings must be merged together to form a single node N
0
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 rep-
resented by node N
0
and its siblings. For example, if point C is to be deleted from
the PR quadtree representing Figure 13.17(b), the resulting node must be merged
with its siblings, and that larger node again merged with its siblings to restore the
PR quadtree to the decomposition of Figure 13.17(a).
Region search is easily performed with the PR quadtree. To locate all points
within radius r of query point Q, begin at the root. If the root is an empty leaf node,
then no data points are found. If the root is a leaf containing a data record, then the
