Algorithm
Development Kit 1.0

Package algs.model.kdtree

Defines the K-dimensional Tree and the optimized TwoDTree variation.

See:
          Description

Interface Summary
IVisitKDNode Provides interface to enable traversals over KD trees to be defined.
IVisitTwoDNode Provides interface to enable traversals over TwoD trees to be defined.
 

Class Summary
CounterKDTree Helper class to simply keep track of the number of selected nodes that are visited by a traversal.
DimensionalComparator Able to compare IMultiPoint objects using a fixed dimensional index to select the value against which to compare.
DimensionalNode Represents a node in the KD-tree that partitions the space by means of a plane that splits the hyperspace into an "above" and a "below" based upon orientation.
HorizontalNode Represents a node in the KD-tree that partitions the space by means of a vertical line at the given y-coordinate.
KDFactory Produces a KD-tree from a given input set using recursive median approach.
KDTraversal Defines a standard inorder traversal of the KDTree and enables subclasses to provide specialized method to take action at each node of the tree.
KDTree Standard unbalanced k-dimensional binary tree.
TwoDFactory Produces a TwoD-tree from a given input set using recursive median approach.
TwoDNode Represents the base class of a node in the TwoD tree.
TwoDTraversal Defines a standard inorder traversal of the TwoDTree and enables subclasses to provide specialized method to take action at each node of the tree.
TwoDTree Standard unbalanced 2-dimensional binary tree.
VerticalNode Represents a node in the 2D-tree that partitions the space by means of a vertical line at the given x-coordinate.
 

Package algs.model.kdtree Description

Defines the K-dimensional Tree and the optimized TwoDTree variation.

KD tree

A KD tree is a space-partitioning data structure to represent a collection of k-dimensional points. The structure offers efficient implementations of the following operations: To provide optimal behavior the KD trees should be balanced, however there is no efficient means to rebalance trees. In fact, the KD tree implementation provided here offers no ability to remove an IMultiPoint once it has been inserted (you can remove all IMultiPoint objects in the tree using the removeAll method). If you choose to dynamically add IMultiPoint objects to the tree, then the standard approach (much like hash tables in fact) to rebalance the tree is to remove all IMultiPoints and insert them in an order that ensures the resulting KD tree is balanced. The KDFactory class offers a static method public static synchronized KDTree generate (IMultiPoint []points) to generate a balanced KD tree using an algorithm that recursively locates medians and inserts the points "above" and "below" the median nodes as needed. The TwoDFactory class offers the same functionality for TwoDTree.

References

Bentley, J. L., Multidimensional binary search trees used for associative searching, Communications ACM 18(9), Sep. 1975, 509–517.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.