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小记