不用std::vector暴力搜因o(n×d)太慢；kd-tree平均o(log n)，但d>30时受维度灾难影响更差；须用nth_element找中位数轮换切分，叶子可设阈值存vector；knn搜索需维护k大小最大堆及距离平方比较。
为什么不用 std::vector<:array d>> 直接暴力搜
因为 KNN 暴力搜索时间复杂度是 O(N×D)，当 N 超过 10⁴、D > 10 时，单次查询就可能卡住主线程。KD-Tree 把平均复杂度压到 O(log N)（理想平衡树），但前提是维度不能太高——通常 D ≤ 20 才明显快于暴力；超过 30 维后，所谓“维度灾难”会让树的剪枝失效，实际性能可能更差。
构造 KD-Tree 必须用中位数切分，不能用平均值
用平均值切分会导致子树严重不平衡，退化成链表，KNN 搜索变回线性扫描。中位数保证左右子树节点数尽可能相等，是维持树高 O(log N) 的关键。
- 每次递归建树时，对当前维度
axis的坐标值调用std::nth_element找中位数，而非std::sort（后者多花 O(N log N)） -
axis按层轮换：第 0 层切第 0 维，第 1 层切第 1 维，… 第D层又切第 0 维，依此类推 - 叶子节点不强制只存 1 个点；可设阈值（如
max_leaf_size = 10），少于该数直接存为 vector，避免过度分裂
KNN 搜索时必须维护候选集 + 当前最近距离，不能只记一个 best
要找 k 个最近邻，就得维持一个大小为 k 的最大堆（或 std::priority_queue），按距离平方排序。否则遇到“先入为主”的远点，会漏掉真正更近的点——尤其在回溯时，另一子树可能藏着多个更优解。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用距离平方比较，避免开方运算（
(a.x-b.x)*(a.x-b.x) + ...） - 进入子树前，算出查询点到该子树对应超平面的距离平方；若该值 ≥ 堆顶距离平方，整个子树可剪枝
- 递归顺序建议：先搜包含查询点的子树，再搜另一侧；这样能更快收紧堆顶距离，提升剪枝率
插入新点或动态更新会破坏平衡，别硬撑在线构建
KD-Tree 天然不适合高频增删。每次插入都重平衡代价太高，而放任不平衡，几十次插入后树高就接近 O(N)，KNN 变慢十倍以上。生产环境里，更稳妥的做法是：
- 数据静态或批量更新时，一次性重建整棵树（
build_tree(points)） - 需要动态能力？改用
nanoflann或FLANN库，它们内部做了惰性重建或森林策略（forest of kd-trees） - 自己手写的话，至少加个 rebuild flag：当插入次数 > 0.1×原始点数，标记需重建，下次查询前统一处理
最易被忽略的一点：所有距离比较必须用平方值，且所有中位数分割必须用 nth_element —— 这两个细节错一个，性能就掉回暴力级别。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
