Java Reference
In-Depth Information
C
A (40, 45)
x
A
D
y
C (70, 10)
B (15, 70)
x
D (69, 50)
B
y
E
F
E (66, 85)
F (85, 90)
(a)
(b)
Figure13.11
Example of a k-d tree. (a) The k-d tree decomposition for a 128
128-unit region containing seven data points. (b) The k-d tree for the region of (a).
space into rectangles that show the extent of where nodes can fall in the various
subtrees.
Searching a k-d tree for the record with a specified xy-coordinate is like search-
ing a BST, except that each level of the k-d tree is associated with a particular dis-
criminator.
Example13.5
Consider searching the k-d tree for a record located at P =
(69; 50). First compare P with the point stored at the root (record A in
Figure 13.11). If P matches the location of A, then the search is successful.
In this example the positions do not match (A's location (40, 45) is not
the same as (69, 50)), so the search must continue. The x value of A is
compared with that of P to determine in which direction to branch. Because
A
x
's value of 40 is less than P's x value of 69, we branch to the right subtree
(all cities with x value greater than or equal to 40 are in the right subtree).
A
y
does not affect the decision on which way to branch at this level. At the
second level, P does not match record C's position, so another branch must
be taken. However, at this level we branch based on the relative y values
of point P and record C (because 1 mod 2 = 1, which corresponds to the
y-coordinate). Because C
y
's value of 10 is less than P
y
's value of 50, we
branch to the right. At this point, P is compared against the position of D.
A match is made and the search is successful.
If the search process reaches a
null
pointer, then that point is not contained
in the tree. Here is a k-d tree search implementation, equivalent to the
findhelp
function of the BST class.
KD
class private member
D
stores the key's dimension.
