Java Reference
In-Depth Information
0
127
0
C
NW
SE
NE
SW
A
B
A
(40,45)
(15,70)
D
C
D
B
(69,50)
(70, 10)
F
E
F
E
(55,80)(80, 90)
127
(B)
(A)
Figure13.16
Example of a PR quadtree. (a) A map of data points. We de-
fine the region to be square with origin at the upper-left-hand corner and sides of
length 128. (b) The PR quadtree for the points in (a). (a) also shows the block
decomposition imposed by the PR quadtree for this region.
it is represented by a PR quadtree consisting of a single leaf node. If the region con-
tains more than a single data point, then the region is split into four equal quadrants.
The corresponding PR quadtree then contains an internal node and four subtrees,
each subtree representing a single quadrant of the region, which might in turn be
split into subquadrants. Each internal node of a PR quadtree represents a single
split of the two-dimensional region. The four quadrants of the region (or equiva-
lently, the corresponding subtrees) are designated (in order) NW, NE, SW, and SE.
Each quadrant containing more than a single point would in turn be recursively di-
vided into subquadrants until each leaf of the corresponding PR quadtree contains
at most one point.
For example, consider the region of Figure 13.16(a) and the corresponding
PR quadtree in Figure 13.16(b). The decomposition process demands a fixed key
range. In this example, the region is assumed to be of size 128128. Note that the
internal nodes of the PR quadtree are used solely to indicate decomposition of the
region; internal nodes do not store data records. Because the decomposition lines
are predetermined (i.e, key-space decomposition is used), the PR quadtree is a trie.
Search for a record matching point Q in the PR quadtree is straightforward.
Beginning at the root, we continuously branch to the quadrant that contains Q until
our search reaches a leaf node. If the root is a leaf, then just check to see if the
node's data record matches point Q. If the root is an internal node, proceed to
the child that contains the search coordinate. For example, the NW quadrant of
Figure 13.16 contains points whose x and y values each fall in the range 0 to 63.
The NE quadrant contains points whose x value falls in the range 64 to 127, and
