KD-Tree

贡献者： int256

　　 KD-Tree（K-Dimension Tree）是一种空间划分数据结构，顾名思义，可以对 $k$ 维空间进行划分。它常被用于高维空间中的搜索，比如范围搜索和最近邻搜索，时间复杂度由 $k$ 和总节点数 $n$ 共同保障。一般当 $n$ 远大于 $2^k$ 时，应用 KD-Tree 的效果是最好的。

　　 KD-Tree 具有二叉搜索树的形态，二叉搜索树上的每个节点都对应 $k$ 维空间内的一个点。其每个子树中的点都在一个 $k$ 维的超长方体内，这个超长方体内的所有点也都在这个子树中。

　　 由主定理可以分析得到，KD-Tree 的复杂度是 $\mathcal O\left(n^{1-\frac 1k}\right)$ 的。

1. 建树

　　 已经知道了这 $n$ 个 $k$ 维空间中的点的坐标，如何建立一颗对应的 KD-Tree？有如下方法：

• 考虑当前要分割的点集，这些点都在一个 $k$ 维超长方体内。若这超长方体内有且仅有一个点，返回这个点。
• 若这个超长方体内有多于 $1$ 个点，考虑对这个超长方体进行分割：
• 1. 选择 $k$ 个维度中的一个。
• 2. 选择一个分割点，这选择的这一维度上的值小于这个点的归入一个超长方体（左子树），其余的归入另一个超长方体（右子树）。
• 3. 将选择的点作为这棵子树的根节点，递归建立左右子树并在过程中维护出需要的信息。

　　 显然如果选择维度是随机的、选择的点也是随机的，这数据结构的复杂度将没有保障。

　　 对于步骤 $1$，我们经常需要讨论各个维度的临近情况，所以希望能在 KD-Tree 每相邻的 $k$ 个深度里都分别有这 $k$ 个维度。故我们考虑这选取维度的方法是轮流选取 $k$ 个维度。另外有一种 “随机化” 的方法是先将 $1$ 至 $k$ 连续赋值给一个数组，后将这个数组随机打乱，然后轮流取这个数组里的每个元素对应的维度。

　　 对于步骤 $2$，考虑 “二分”，每次取的这个分割点位于中位是最佳的。不难想到使用这优化后将限制 KD-Tree 的深度在 $\mathcal O\left(\log n\right)$ 量级，更准确地说其实是在 $\log n + \mathcal O(1)$ 量级。

2. 高维操作

　　 在维护高维矩形区域内的所有点的某些信息过程中，记录下每个节点子树内每一维度上的坐标的最大值和最小值。

• 如果当前子树对应的矩形与所求矩形完全相离，也就是没有交点，则直接返回，不继续搜索这棵子树的子树；
• 如果当前子树对应的矩形完全包含在所求矩形内，返回当前子树内所有点的权值和；否则，判断当前点是否在所求矩形内，更新答案并递归在左右子树中查找答案（这过程类似于线段树）。

3. 插入操作

　　 类似于二叉搜索树的，对于要被插入的节点，根据各个维度上的划分确定它在左子树还是在右子树，之后递归插入即可。

4. 删除操作

　　 如果要删除的节点是叶子节点，直接递归访问到然后直接删除，再在回溯过程中更新这访问的整条链的信息就可以。

　　 首先递归找到这节点，然后考虑这个节点的左右子树，可以在左子树上取这一维度上最大的点代替这点，然后递归重建左子树。如果没有左子树，就考虑右子树的这维度上最小的点即可。

　　 处理完以这节点为根节点的子树后，从这节点回溯的过程中更新整棵树的信息。

5. 最邻近点

　　 注意：KD-Tree 解决该问题的复杂度最坏是 $\mathcal O(n)$ 的，只不过由于剪枝而快速很多。

　　 具体剪枝的方法是： 维护一个子树中的所有节点在每一维上的坐标的取值范围。假设当前已经找到的最近点对的距离是 $\mathscr x_0$，如果查询的点到子树内所有点都包含在内的超长方体的最近距离大于等于 $\mathscr x_0$，则在这个子树内一定没有答案，搜索时不进入这个子树。

　　 另外也可以考虑启发式搜索，估价函数可以取为查询点到子树对应的超长方体的距离。对于当前点对的距离，若估价函数大于等于当前答案，就无需访问此子树。对于两颗子树都小于答案的情况，优先访问距离小的子树。