「OI」k-D Tree

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

在结点数 $n$ 远大于 $2^n$ 时,应用 $\texttt{k-D Tree}$ 的时间效率很好。

在算法竞赛的题目中,一般有 $k=2$。在分析时间复杂度时,将认为 $k$ 是常数。

k-D Tree 数据结构

建树

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

假设我们已经知道了 $k$ 维空间内的 $n$ 个不同的点的坐标,要将其构建成一棵 $\texttt{k-D Tree}$,步骤如下:

  • 若当前超长方体中只有一个点,返回这个点对应编号。
  • 选择一个维度,将当前超长方体按照这个维度分成两个超长方体。
  • 选择切割点:在选择的维度上选择一个点,这一维度上的值小于这个点的归入一个超长方体(左子树),其余的归入另一个超长方体(右子树)。
    • 这里有一点注意事项。分割点必然选取这一维度的坐标中位数的对应点,就是排序后中间的那个点,但是排序的复杂度为 $\Theta(n\log_2n)$,切割 $\Theta(\log_2n)$ 次,时间复杂度是 $\Theta(n\log_2^2n)$。
    • 但是排序实际上浪费了许多信息,我们只需要中间点即可。
    • $\texttt{STL}$ 提供了一个函数 std::nth_element 可以实现把整个序列分成三部分:左边、中间、右边,并且保证左边不大于中间,右边不小于中间,正好符合要求。std::nth_element 基于分治思想实现,单次操作 $n$ 个项的时间复杂度为 $\Theta(n)$,切割 $\Theta(\log_2n)$ 次,时间复杂度是 $\Theta(n\log_2n)$,更快了。
  • 将选择的点作为这棵子树的根节点,递归对分出的两个超长方体构建左右子树,维护子树的信息。

其实按照上述步骤建树以后,$\texttt{k-D Tree}$ 操作的时间复杂度的影响因素只有两个:

  1. 树的平衡度;
  2. 每次选择的维度;

下面着重讨论这两个方面。

树的平衡度

如果树不平衡(甚至树直接退化成了链),那么单次操作的时间复杂度为 $\Theta(n)$,显然太慢。

于是考虑解决树不平衡的问题。$\texttt{k-D Tree}$ 之所以会不平衡,是因为我们会往里面插入新的结点,如果光往左子树里插,就会导致树的左子树“粗壮”。发现这与二叉搜索树的情形类似,于是考虑用类似的方法解决问题。

常用的是替罪羊树的方法:把树拍扁重建

每次选择的维度

有多种方法选择维度。

  1. 不选择
    这怎么可能是 $\texttt{k-D Tree}$,肯定会爆炸的。
  2. 随机选择
    这个建树的复杂度比较玄学,一般不容易通过题目。
  3. 每次轮换选择
    这个写起来方便,但是容易被特殊数据卡死,时间复杂度为 $\Theta(n\log_2n)$。
  4. 每次选择方差最大的维度
    这个最科学,并且理论上这样使得 启发式搜索 的耗时最短,但是建树时候要计算方差,常数较大,容易被卡(本质上是时间复杂度变成了 $\Theta(nk\log_2n)$)。

插入操作

比较简单,正常的插入操作,就是动态开点的树。

查询操作

视情况而定,具体操作具体分析,大部分题目的查询操作都是启发式搜索,某些卡树套树空间,卡 CDQ 分治的毒瘤题除外。

题目推荐

洛谷 P4148
洛谷 P2479