k-d Tree

形式陈述 ​

构造与区域不变量 ​

固定维数 $d\ge 1$ 和每条点记录的唯一 ID。kd-tree 是一棵二叉树理路二叉树Binary tree由空树或根节点及左右两个子树槽位递归组成的有限结构；单孩子所在的左右位置也属于树形。；本页静态版本在逐层循环的坐标轴 $0,\dots ,d-1$ 上，以 $(x_j,\mathrm{id})$ 为键选中位顺序统计量理路顺序统计量Order statistic有限样本按键排序后第 k 个位置的值，保留重复出现的次数。。中位记录存于节点，其余记录按键唯一分入左右子树，规模相差至多一；原坐标在左侧不大于切分值、右侧不小于它，坐标相同时仍不重复记录。确定性线性选择理路选择算法Selection algorithm在未排序序列中求第 k 小元素而无需完全排序的算法族。可构造高度 $O(\log (n+1))$ 的树。每个节点隐式或显式对应一个轴对齐区域，子区域由父区域切成两半。

范围与最近邻 ​

用于正交范围报告理路正交范围查询Orthogonal range searching在固定维点集中对轴对齐盒执行报告、计数、判空或聚合查询。时，区域与查询盒不交则剪枝，完全包含则报告整棵子树，否则递归。对上述固定循环轴、中位平衡的版本，二维范围报告界为 $O(\sqrt{n}+k)$；固定 $d\ge 2$ 时为 $O(n^{1-1/d}+k)$。为使重复坐标也服从分割分析，可在每一轴按 $(x_j,\mathrm{id})$ 的秩表示点，用该轴 lower/upper bound 将原查询区间转为秩区间。报告成员不变，而各轴秩互异；预处理保存这些次序，查询转换另花 $O(d\log (n+1))$。对固定 $d\ge 2$，它被上述界吸收；一维直接采用区间搜索的 $O(\log (n+1)+k)$ 界。任意换轴启发式或仅有高度平衡，不自动满足同一个循环轴分析。

界的来源是查询边界穿过多少个区域。在互异秩的表示中，固定一张垂直于某轴的查询边界：沿该轴切分时，它至多穿过一个子区域的内部；沿其他轴切分时至多穿过两个。每 $d$ 层至多留下 $2^{d-1}$ 个子问题，各含至多约 $n/2^d$ 条记录，故边界工作为 $O(n^{1-1/d})$。固定维盒子只有 $2d$ 张边界，完全包含的子树则按实际输出收费，得到上述 $+k$ 项。开闭边界用秩区间的一致端点约定处理。

欧氏最近邻另外选用原坐标的标准内积理路内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。；秩坐标只用于范围报告，不能替代真实距离。非空树先沿分割朝查询点所在一侧下降到叶或空孩子，再回溯检查节点点。初始最好距离为 $+\mathrm{\infty }$，只有找到真实点才更新；空树直接返回不存在。回溯时以当前最好距离为半径；若另一子区域到查询点的最小距离不小于最好值就剪枝，否则必须搜索。这里返回任意一个最近点；若需报告全部并列最近点，下界等于当前最好值时也不能剪枝。正确性不依赖“通常很近”，而依赖包围区域给出的下界。