Build

Median split on x-axis at root. Left/right subtrees split on y. Alternate. O(N log N) with median-of-medians or sort.

Advertisement

NN query

Point nearest(KdNode node, Point q, Point best, int depth) {
  if (node == null) return best;
  double d = dist(q, node.p);
  if (d < dist(q, best)) best = node.p;
  int axis = depth % k;
  KdNode first = (q.get(axis) < node.p.get(axis)) ? node.left : node.right;
  KdNode other = (first == node.left) ? node.right : node.left;
  best = nearest(first, q, best, depth + 1);
  if (Math.abs(q.get(axis) - node.p.get(axis)) < dist(q, best))
    best = nearest(other, q, best, depth + 1);
  return best;
}
Advertisement

Complexity

Build O(N log N). NN query O(log N) expected in 2D-3D. Degrades to O(N^(1-1/d)) at high d.

Curse of dimensionality

d ≥ 10-20: k-d tree no better than linear scan. Use LSH, HNSW, or IVF-based methods.