121. Introducing the K-D Tree data structure
A K-D Tree (also referred to as a K-dimensional tree) is a data structure that is a flavor of Binary Search Tree (BST) dedicated to holding and organizing points/coordinates in a K-dimensional space (2-D, 3-D, and so on). Each node of a K-D Tree holds a point representing a multi-dimensional space. The following snippet shapes a node of a 2-D Tree:
private final class Node {
private final double[] coords;
private Node left;
private Node right;
public Node(double[] coords) {
this.coords = coords;
}
...
}
Instead of a double[] array, you may prefer java.awt.geom.Point2D, which is dedicated to representing a location in (x, y) coordinate space.
Commonly, K-D Trees are useful for performing different kinds of searches such as nearest-neighbor searches and range queries. For instance, let’s assume a 2-D space and a bunch of (x, y) coordinates in this space:
double[][] coords = {
{3, 5}, {1, 4}, {5, 4...