一、为什么学 KD 树？
Mermaid · 渲染中（下方为源码）
graph TD A[k维点集] --> B[按 depth%k 轮换切分] B --> C[左小右大] C --> D[最近邻/范围查询]
KD 树是多维空间（k 维）的二叉搜索树，用于高效处理：
- 最近邻查询（NN）：给定点找最近的点
- 范围查询（Range Search）：找出矩形/超立方体内的所有点
- 低维（k 较小，通常 ≤ 20）下近似 O(log n)，高维退化为 O(n)
二、结构
- 每个节点代表一个 k 维点
- 按"深度 mod k"选择切分维度，在该维度中位数处分裂
- 左子树维度值更小，右子树更大
三、建树与最近邻查询
class Node {
double[] p; int dim; Node left, right;
}
Node build(double[][] pts, int l, int r, int depth) {
if (l > r) return null;
int d = depth % pts[0].length;
int mid = (l + r) / 2;
Arrays.sort(pts, l, r + 1, (a, b) -> Double.compare(a[d], b[d]));
Node node = new Node(); node.p = pts[mid]; node.dim = d;
node.left = build(pts, l, mid - 1, depth + 1);
node.right = build(pts, mid + 1, r, depth + 1);
return node;
}
double best = Double.MAX_VALUE;
void nn(Node u, double[] q) {
if (u == null) return;
double dist = 0;
for (int i = 0; i < q.length; i++) dist += (u.p[i] - q[i]) * (u.p[i] - q[i]);
best = Math.min(best, dist);
int d = u.dim;
Node near = q[d] < u.p[d] ? u.left : u.right;
Node far = q[d] < u.p[d] ? u.right : u.left;
nn(near, q);
// 若超平面可能含更近点，则搜索另一侧
if ((q[d] - u.p[d]) * (q[d] - u.p[d]) < best) nn(far, q);
}