kd-tree(KDT) 时间复杂度证明

kd-tree 是一种可以高效处理 $k$ 维空间的数据结构

在算法竞赛类的题目中一般有 $k=2$

还有个比较有趣的结论，当 $k=1$ 时其实它就是一棵线段树

下文中的 $n$ 为kd-tree中的结点数量， $k$ 为kd-tree的维度

---

一、建树

一般建树有三种

1. 随机划分（玄学）
2. 轮换划分：每个维度轮着划分
3. 方差划分：优先划分方差较大的维度

我可不想分析玄学的划分

1. 轮换划分

显然有递推式 $T(n) = 2T(n/2) + O(n)$

根据主定理，有 $a=2,b=2,\log_b{a}=1,f(n)=O(n)$

$\because \exists \epsilon \ge 0$ 使得 $f(n) = \Theta(n^{\log_b{a}}\log^{\epsilon}n)$ ，此时 $\epsilon = 0$

$\therefore T(n) = \Theta(n\log n)$

2. 方差划分

注意到 $T(n) = 2T(n/2) + O(kn)$

因此时间复杂度为 $T(n) = \Theta(nk\log n)$

一般在算法竞赛中，由于 $k$ 很小（一般 $k=2$ ），因此有

$T(n) = \Theta(n\log n)$

本划分方法能较好保证树高，且不易被卡

---

二、插入&删除

一般采用替罪羊树的插入&删除操作

利用重构子树的方式维持平衡

均摊复杂度为 $O(\log n)$

证明可以去看替罪羊树的，这里先留个坑以后补上

---

三、Range Query

个人感觉算kd-tree的核心操作吧

支持将一个超长方体区域内的点划分为 $O(\sqrt{n})$ 个点所管辖的区域

称 $R$ 为待查询的超长方体，则对于树上结点所管辖的超长方体分类，存在以下三种情况

1. 与 $R$ 的交集为空

2. 全部包含于 $R$ 内

3. 与 $R$ 有交集且不包含于 $R$

算法在查询过程中，碰到第1,2类点不会继续递归其子树

因此算法的时间复杂度就与第3类点的数量有关

我们以轮换划分来分析，则在相邻的 $k$ 轮中，分别对每一维进行了划分

显然会产生 $2^k$ 个部分，每个部分的大小均为原来的 $\dfrac{1}{2^k}$

由于一个用于划分的超平面至多跨越 $2^{k-1}$ 个部分（可以由归纳法证明，此处略）

则有 $T(n) = 2^{k-1}T(n/2^k)+O(1)$

根据主定理，有 $a=2^{k-1},b=2^k,\log_b{a} = \dfrac{k-1}{k},f(n)=O(1)$

$\because \exists \epsilon > 0$ 使得 $f(n) = O(n^{\log_b{a}-\epsilon})$ ，此时 $\epsilon = \dfrac{k-1}{k}$

$\therefore T(n) = \Theta\left(n^{1-\frac{1}{k}}\right)$

当 $k=2$ 时， $T(n) = \Theta(\sqrt{n})$

---

参考文献

[1] KDT小记