k-d Tree

构造与区域不变量 ​

每个节点选择坐标轴（常循环 $0,\dots ,d-1$），以该轴中位顺序统计量公理库顺序统计量Order statistic有限有序样本排序后第 k 个位置的元素。作切分点；左子树坐标不大于切分值，右子树不小于它。线性选择中位数可构造高度 $O(\log n)$ 的静态树。每个节点隐式或显式对应一个轴对齐区域，子区域由父区域切成两半。

范围与最近邻 ​

正交范围报告时，区域与查询盒不交则剪枝，完全包含则报告整棵子树，否则递归。二维平衡 kd-tree 的经典范围报告界为 $O(\sqrt{n}+k)$；固定更高维的指数依维数变化。

最近邻先下降到含查询点的叶，回溯时以当前最好距离为半径；若另一子区域到查询点的最小距离不小于最好值就剪枝，否则必须搜索。正确性不依赖“通常很近”，而依赖包围区域给出的下界。

地理索引例子 ​

门店点按经、纬度交替切分。查询一个轴对齐地图视窗时，西侧节点区域若完全在视窗外可整棵跳过；最近门店查询则用当前候选距离判断是否有必要跨越切分线。

维数灾难 ​

最近邻最坏可访问全部 $n$ 个点，不是无条件 $O(\log n)$。高维中查询球常与大量区域相交，剪枝退化；重复坐标、极偏数据和选择非中位切分也会破坏形状。动态插入若不重平衡，树可能成链；使用方差轴是启发式，不改变最坏结论。

构建成本与距离下界 ​

每层若对当前子集线性选择中位数，所有节点一层总工作 $O(n)$，平衡高度给构建 $O(n\log n)$；每层重新完整排序会增加不必要成本。重复坐标可用另一坐标或稳定 ID tie-break，确保每个点只进入一侧。

欧氏最近邻中，查询点到轴对齐包围盒的最小距离由各坐标超出区间的量平方和给出。只有该下界已不小于当前最好距离时才能剪枝；只比较查询点与切分平面的距离，在节点存有更紧包围盒时虽安全但可能少剪枝，反向用错误上界则会漏答案。

最近邻查询的堆栈状态 ​

查询点 $q$ 时先沿包含 $q$ 的一侧下降，维护目前最近距离 $R$。回溯节点时更新切分点距离，再计算 $q$ 到另一子区域包围盒的最小可能距离 $d_{box}$：只有 $d_{box}<R$ 才进入另一侧。剪枝证书是区域下界，而不是“另一侧离切分平面较远”的直觉判断。

例如二维节点按 $x=5$ 切分，$q=(6,2)$，当前最近距离为 3。仅凭到平面距离 1 不能剪左侧；若左子区域的 $y$ 范围为 $[10,20]$，包围盒距离至少 8，才可安全跳过。反过来，若只存切分轴、不存区域边界，使用欧氏距离剪枝时必须从祖先约束重建盒子。

平衡构造保证树高 $O(\log n)$，却不保证访问节点数对数。精确最近邻在高维或点集中于薄壳时可能检查线性多节点；随机近似搜索通过限制回溯预算改变的是答案保证，而不是同一算法的常数优化。

范围报告查询对与矩形相交的区域递归，对完全包含的区域可直接报告整棵子树；若节点未存子树点列表，仍需遍历输出，成本自然含 $+k$。空区域和边界相切时应按闭/开区间约定统一处理。

删除若仅打墓碑会让高度与区域包围盒逐渐失真。动态 k-d tree 常按失衡或墓碑比例重建子树，这提供的是摊还或经验性能，不能与静态中位数构造的最坏高度混写。

参考资料

• Jon Bentley, Multidimensional Binary Search Trees Used for Associative Searching, CACM, 1975.
• Mark de Berg et al., Computational Geometry, multidimensional searching.