Java Reference
In-Depth Information
location of the data point is examined to determine if it falls within the circle. If
the root is an internal node, then the process is performed recursively, but only on
those subtrees containing some part of the search circle.
Let us now consider how the structure of the PR quadtree affects the design
of its node representation. The PR quadtree is actually a trie (as defined in Sec-
tion 13.1). Decomposition takes place at the mid-points for internal nodes, regard-
less of where the data points actually fall. The placement of the data points does
determine whether a decomposition for a node takes place, but not where the de-
composition for the node takes place. Internal nodes of the PR quadtree are quite
different from leaf nodes, in that internal nodes have children (leaf nodes do not)
and leaf nodes have data fields (internal nodes do not). Thus, it is likely to be ben-
eficial to represent internal nodes differently from leaf nodes. Finally, there is the
fact that approximately half of the leaf nodes will contain no data field.
Another issue to consider is: How does a routine traversing the PR quadtree
get the coordinates for the square represented by the current PR quadtree node?
One possibility is to store with each node its spatial description (such as upper-left
corner and width). However, this will take a lot of space — perhaps as much as the
space needed for the data records, depending on what information is being stored.
Another possibility is to pass in the coordinates when the recursive call is made.
For example, consider the search process. Initially, the search visits the root node
of the tree, which has origin at (0, 0), and whose width is the full size of the space
being covered. When the appropriate child is visited, it is a simple matter for the
search routine to determine the origin for the child, and the width of the square is
simply half that of the parent. Not only does passing in the size and position infor-
mation for a node save considerable space, but avoiding storing such information
in the nodes enables a good design choice for empty leaf nodes, as discussed next.
How should we represent empty leaf nodes? On average, half of the leaf nodes
in a PR quadtree are empty (i.e., do not store a data point). One implementation
option is to use a
null
pointer in internal nodes to represent empty nodes. This
will solve the problem of excessive space requirements. There is an unfortunate
side effect that using a
null
pointer requires the PR quadtree processing meth-
ods to understand this convention. In other words, you are breaking encapsulation
on the node representation because the tree now must know things about how the
nodes are implemented. This is not too horrible for this particular application, be-
cause the node class can be considered private to the tree class, in which case the
node implementation is completely invisible to the outside world. However, it is
undesirable if there is another reasonable alternative.
Fortunately, there is a good alternative. It is called the Flyweight design pattern.
In the PR quadtree, a flyweight is a single empty leaf node that is reused in all places
where an empty leaf node is needed. You simply have all of the internal nodes with
empty leaf children point to the same node object. This node object is created once
