手写KD-Tree易搜错最近邻，主因是回溯时漏判另一子树可能性；建树须用真中位数（partition或排序取中），搜索时需严格按轴距与当前最优距比较来决定是否跨边。
为什么手写 KD-Tree 很容易搜错最近邻
手写 KD-Tree 最近邻搜索失败，90% 是因为递归回溯时漏判了“另一侧子树可能含更近点”的情况。标准实现里 find_nearest 必须在进入子节点后，再根据当前维度分割超平面到查询点的距离，决定是否要跨边搜索另一子树——这个判断不能省略，也不能只靠距离比较，得用 abs(query[depth % k] - node->value[depth % k]) 和当前最优距离比较。
建树时中位数必须真中位数，不能用 std::nth_element 随便分
std::nth_element 能做到 O(n) 分割，但不保证左侧全 ≤ 中位数、右侧全 ≥ 中位数（尤其存在重复值时），会导致树不平衡或后续搜索越界。正确做法是：先调用 std::nth_element 找出中位数位置，再用 std::partition 严格分离；或者直接排序后取 begin + size/2，对中小规模数据（
- 维度
k一般取 2 或 3，超过 5 维后 KD-Tree 效果急剧下降，别硬上 - 建树递归深度建议加保护，比如
if (end - begin ，避免栈溢出 - 节点结构推荐存原始索引而非拷贝坐标，节省内存且方便对接外部数据数组
最近邻搜索必须维护一个“当前最近距离平方”，全程不開根号
开根号是浮点重操作，且比较大小完全可用平方距离替代。所有距离计算统一用 dist_sq = 0; for (int i = 0; i 。搜索过程中，一旦某子树的超平面距离平方（即 (query[axis] - node->value[axis]) * (query[axis] - node->value[axis])）已经 ≥ 当前最优距离平方，就跳过整个子树。
关键细节：更新最优解后，必须重新检查是否需要搜索“另一侧”——不是“如果更近才搜”，而是“如果超平面距离
边界情况：空树、单点、查询点与节点重合、多维重复坐标
空树直接返回无效索引；单点只需一次距离计算；查询点与节点重合时，距离为 0，但不能提前终止——仍需检查另一侧是否也有 0 距离点（比如多个点坐标完全相同）。重复坐标在中位数分割时极易导致左右子树极度不均，建议在建树前对输入做轻量去重或加微小扰动（如 + 1e-9 * i），比硬扛更可靠。
最易被忽略的是：当使用索引间接访问坐标时，query 数组和节点存储的坐标数组必须是同一份内存布局，否则 node->value[axis] 可能读错维度。调试时先打一行 printf("axis=%d, val=%.3f\n", axis, node->value[axis]); 看是否符合预期。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
