KdTree

Extension of the binary search tree that is used to partition k-dimensional points into a vector space.

Common operations:

• Contains - used to determine whether a point is represented in the vector space
• Delete, Put - used to remove and place points into the vector space respectively

Queries:

• RangeSearch - returns all the points in the tree within the search area
• NearestNeighbour - returns the point in the tree closest to the argument

If the points to be in the tree are known in advance KdTree can be used to generate a fairly balanced tree.