Java Reference
In-Depth Information
privateEfindhelp(KDNode<E>rt,int[]key,intlevel){
if(rt==null)returnnull;
Eit=rt.element();
int[]itkey=rt.key();
if((itkey[0]==key[0])&&(itkey[1]==key[1]))
returnrt.element();
if(itkey[level]>key[level])
returnfindhelp(rt.left(),key,(level+1)%D);
else
returnfindhelp(rt.right(),key,(level+1)%D);
}
Inserting a new node into the k-d tree is similar to BST insertion. The k-d tree
search procedure is followed until a
null
pointer is found, indicating the proper
place to insert the new node.
Example13.6
Inserting a record at location (10, 50) in the k-d tree of
Figure 13.11 first requires a search to the node containing record B. At this
point, the new record is inserted into B's left subtree.
Deleting a node from a k-d tree is similar to deleting from a BST, but slightly
harder. As with deleting from a BST, the first step is to find the node (call it N)
to be deleted. It is then necessary to find a descendant of N which can be used to
replace N in the tree. If N has no children, then N is replaced with a
null
pointer.
Note that if N has one child that in turn has children, we cannot simply assign N's
parent to point to N's child as would be done in the BST. To do so would change the
level of all nodes in the subtree, and thus the discriminator used for a search would
also change. The result is that the subtree would no longer be a k-d tree because a
node's children might now violate the BST property for that discriminator.
Similar to BST deletion, the record stored in N should be replaced either by the
record in N's right subtree with the least value of N's discriminator, or by the record
in N's left subtree with the greatest value for this discriminator. Assume that N was
at an odd level and therefore y is the discriminator. N could then be replaced by the
record in its right subtree with the least y value (call it Y
min
). The problem is that
Y
min
is not necessarily the leftmost node, as it would be in the BST. A modified
search procedure to find the least y value in the left subtree must be used to find it
instead. The implementation for
findmin
is shown in Figure 13.12. A recursive
call to the delete routine will then remove Y
min
from the tree. Finally, Y
min
's record
is substituted for the record in node N.
Note that we can replace the node to be deleted with the least-valued node
from the right subtree only if the right subtree exists. If it does not, then a suitable
replacement must be found in the left subtree. Unfortunately, it is not satisfactory
to replace N's record with the record having the greatest value for the discriminator
in the left subtree, because this new value might be duplicated.
If so, then we
