$\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}$ 操作的时间复杂度的影响因素只有两个:
- 树的平衡度;
- 每次选择的维度;
下面着重讨论这两个方面。
树的平衡度
如果树不平衡(甚至树直接退化成了链),那么单次操作的时间复杂度为 $\Theta(n)$,显然太慢。
于是考虑解决树不平衡的问题。$\texttt{k-D Tree}$ 之所以会不平衡,是因为我们会往里面插入新的结点,如果光往左子树里插,就会导致树的左子树“粗壮”。发现这与二叉搜索树的情形类似,于是考虑用类似的方法解决问题。
常用的是替罪羊树的方法:把树拍扁重建。
每次选择的维度
有多种方法选择维度。
- 不选择
这怎么可能是 $\texttt{k-D Tree}$,肯定会爆炸的。 - 随机选择
这个建树的复杂度比较玄学,一般不容易通过题目。 - 每次轮换选择
这个写起来方便,但是容易被特殊数据卡死,时间复杂度为 $\Theta(n\log_2n)$。 - 每次选择方差最大的维度
这个最科学,并且理论上这样使得 启发式搜索 的耗时最短,但是建树时候要计算方差,常数较大,容易被卡(本质上是时间复杂度变成了 $\Theta(nk\log_2n)$)。
插入操作
比较简单,正常的插入操作,就是动态开点的树。
查询操作
视情况而定,具体操作具体分析,大部分题目的查询操作都是启发式搜索,某些卡树套树空间,卡 CDQ 分治的毒瘤题除外。
题目推荐
洛谷 P4148
洛谷 P2479
近期评论