K-D Tree

k-D Tree(KDT , k-Dimension Tree) 是一种可以 高效处理维空间信息 的数据结构。

在结点数远大于时，应用 k-D Tree 的时间效率很好。

在算法竞赛的题目中，一般有。在本页面分析时间复杂度时，将认为是常数。

建树

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

假设我们已经知道了维空间内的个不同的点的坐标，要将其构建成一棵 k-D Tree，步骤如下：

若当前超长方体中只有一个点，返回这个点。
选择一个维度，将当前超长方体按照这个维度分成两个超长方体。
选择切割点：在选择的维度上选择一个点，这一维度上的值小于这个点的归入一个超长方体（左子树），其余的归入另一个超长方体（右子树）。
将选择的点作为这棵子树的根节点，递归对分出的两个超长方体构建左右子树，维护子树的信息。

为了方便理解，我们举一个时的例子。

其构建出 k-D Tree 的形态可能是这样的：

其中树上每个结点上的坐标是选择的分割点的坐标，非叶子结点旁的或是选择的切割维度。

这样的复杂度无法保证。对于两步，我们提出两个优化：

选择的维度要满足其内部点的分布的差异度最大，即每次选择的切割维度是方差最大的维度。
每次在维度上选择切割点时选择该维度上的 中位数，这样可以保证每次分成的左右子树大小尽量相等。

可以发现，使用优化后，构建出的 k-D Tree 的树高最多为。

现在，构建 k-D Tree 时间复杂度的瓶颈在于快速选出一个维度上的中位数，并将在该维度上的值小于该中位数的置于中位数的左边，其余置于右边。如果每次都使用 sort 函数对该维度进行排序，时间复杂度是的。事实上，单次找出个元素中的中位数并将中位数置于排序后正确的位置的复杂度可以达到。

我们来回顾一下快速排序的思想。每次我们选出一个数，将小于该数的置于该数的左边，大于该数的置于该数的右边，保证该数在排好序后正确的位置上，然后递归排序左侧和右侧的值。这样的期望复杂度是的。但是由于 k-D Tree 只要求要中位数在排序后正确的位置上，所以我们只需要递归排序包含中位数的一侧。可以证明，这样的期望复杂度是的。在 algorithm 库中，有一个实现相同功能的函数 nth_element()，要找到 s[l] 和 s[r] 之间的值按照排序规则 cmp 排序后在 s[mid] 位置上的值，并保证 s[mid] 左边的值小于 s[mid]，右边的值大于 s[mid]，只需写 nth_element(s+l,s+mid,s+r+1,cmp)。

借助这种思想，构建 k-D Tree 时间复杂度是的。

插入/删除

如果维护的这个维点集是可变的，即可能会插入或删除一些点，此时 k-D Tree 的平衡性无法保证。由于 k-D Tree 的构造，不能支持旋转，类似与 FHQ Treap 的随机优先级也不能保证其复杂度，可以保证平衡性的手段只有类似于

替罪羊树的重构思想。

我们引入一个重构常数，对于 k-D Tree 上的一个结点，若其有一个子树的结点数在以为根的子树的结点数中的占比大于，则认为以为根的子树是不平衡的，需要重构。重构时，先遍历子树求出一个序列，然后用以上描述的方法建出一棵 k-D Tree，代替原来不平衡的子树。

在插入一个维点时，先根据记录的分割维度和分割点判断应该继续插入到左子树还是右子树，如果到达了空结点，新建一个结点代替这个空结点。成功插入结点后回溯插入的过程，维护结点的信息，如果发现当前的子树不平衡，则重构当前子树。

如果还有删除操作，则使用 惰性删除，即删除一个结点时打上删除标记，而保留其在 k-D Tree 上的位置。如果这样写，当未删除的结点数在以为根的子树中的占比小于时，同样认为这个子树是不平衡的，需要重构。

类似于替罪羊树，带重构的 k-D Tree 的树高仍然是的。

邻域查询

例题luogu P1429 平面最近点对（加强版）

给定平面上的个点，找出平面上最近两个点对之间的

欧几里得距离。

首先建出关于这个点的 2-D Tree。

枚举每个结点，对于每个结点找到不等于该结点且距离最小的点，即可求出答案。每次暴力遍历 2-D Tree 上的每个结点的时间复杂度是的，需要剪枝。我们可以维护一个子树中的所有结点在每一维上的坐标的最小值和最大值。假设当前已经找到的最近点对的距离是，如果查询点到子树内所有点都包含在内的长方形的最近距离大于等于，则在这个子树内一定没有答案，搜索时不进入这个子树。