第 16 章四叉树与 K-D 树¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

16.1 均匀空间划分¶

动机¶

假设二维空间中有许多 Body 对象，例如图中的黄色太阳点：

我们可能需要回答两类问题。

二维范围查询¶

某个矩形区域内有多少对象？例如图中绿色矩形覆盖了哪些太阳。

第一次尝试：哈希表¶

若所有太阳存放在普通哈希表中，桶位置与空间坐标没有有用关系。为了找最近邻，必须检查全部 \(N\) 个对象，因此耗时 \(\Theta(N)\)。

我们希望利用对象的空间位置，避免每次都扫描全集。

第二次尝试：均匀划分¶

哈希表的问题在于桶号近似随机。可以让桶号只由坐标决定：在整个图像空间上覆盖一个固定网格，例如 \(4\times4\)。

这种方法也称为空间哈希（spatial hashing）。对象提供 getX() 与 getY()，结构根据坐标计算它属于哪个网格桶，而不是调用普通 hashCode()。

于是：

范围查询只检查与目标矩形相交的桶，例如图中的 5、6、9、10。
最近邻查询先检查查询点所在桶，再逐圈扩展到相邻桶。

如果对象均匀分布，\(4\times4\) 网格平均能把候选数量减少到原来的约 \(1/16\)。实践中会明显更快，但：

\[\frac{N}{16}=\Theta(N)\]

渐近复杂度仍然是线性的。固定网格还会面临另一个问题：某些区域非常拥挤，另一些区域几乎为空。下一节将让空间划分能够根据数据密度自适应。

16.2 四叉树¶

第三次尝试：四叉树¶

只按 X 或只按 Y 建树¶

搜索树相对于哈希表的重要优势，是显式维护元素顺序。例如在 BST 中找最小值只需 \(\Theta(\log N)\)，而哈希表需要 \(\Theta(N)\)。

但二维对象很难定义唯一的“大小”。一个点可能在 X 方向更小、Y 方向却更大。例如图中 Mars 的 X 坐标小于 Earth，但 Y 坐标大于 Earth。

若只按 X 坐标构建 BST，就得到 X 树：

当查询要求 x < -1 时，从根向左后，整个右子树都可以跳过。这相当于把搜索空间限制在某个矩形内。安全地跳过不可能包含答案的子树，称为剪枝（pruning）。

但 X 树对 Y 条件无能为力；按 Y 查询可能仍需遍历所有结点。Y 树则正好相反。因此只优化一个维度，会让另一个维度的查询退化为 \(\Theta(N)\)。

四叉树¶

四叉树同时沿 X 和 Y 方向划分空间。

每个结点把自己负责的区域分成四个象限：

西北（NW）
东北（NE）
东南（SE）
西南（SW）

若点 B 位于点 A 的东北象限，插入时就沿 A 的 NE 孩子方向继续。与 BST 一样，插入顺序会影响四叉树的拓扑结构。

四叉树本质上是一种分层的空间划分。与固定网格不同，点密集的区域会被继续细分，稀疏区域则保持较粗的划分，因此常能获得更好的实际性能。

使用四叉树进行范围查询¶

每个结点拥有四个空间子区域。给定查询矩形，可以判断它与哪些象限相交，只递归探索可能相交的子树，其余象限全部剪枝。

例如绿色矩形只位于当前结点的东北象限，就无需访问 NW、SE 和 SW 子树。

四叉树非常适合二维空间，因为二维恰好产生四个象限。但若维度继续升高，每层孩子数量会指数增长。下一节介绍更容易推广到高维的 K-D 树。

16.3 K-D 树¶

K-D 树把分层空间划分推广到 \(K\) 个维度。它不会在一层同时切分所有维度，而是逐层轮换当前比较维度。

在二维情况下：

第 1 层按 X 坐标划分；
第 2 层按 Y 坐标划分；
第 3 层再次按 X；
第 4 层再次按 Y；
依此类推。

第一张图强调树的层次和每层使用的划分轴，第二张图展示对应的二维空间分区。执行算法时，应主要依据树结构，因为只有树结点记录当前层使用哪个维度。

三维 K-D 树每三层轮换 X、Y、Z；更高维同理。无论维度多高，每次划分都只有“小于”和“大于等于”两侧，因此 K-D 树始终是二叉树。

插入时若某个坐标与分割值相等，需要固定一种一致的破平局规则，例如总是进入右子树。

可通过这些演示幻灯片查看插入过程。

使用 K-D 树寻找最近邻¶

给定查询点，最近邻搜索的基本过程：

从根开始，把当前点记录为 best，其距离作为当前待击败分数。
根据当前结点的划分轴，优先进入查询点所在的一侧。
在递归返回时，计算查询点到另一侧空间边界的最短可能距离。
若这个最短距离已经不小于当前最佳距离，则另一侧不可能出现更优点，直接剪枝。
否则，另一侧仍有可能包含更近的点，必须继续搜索。
递归结束后，best 就是最近邻。

紫色虚线表示查询点到待检查区域边界的最短距离。它是决定能否剪枝的关键下界。

逐步演示见最近邻幻灯片。

总结¶

固定网格简单，但无法适应密度不均匀的数据。
四叉树同时按 X、Y 划分，适合二维范围查询。
K-D 树逐层轮换维度，容易扩展到任意维度。
范围查询和最近邻搜索都依赖空间下界进行剪枝。
实际性能高度依赖树是否平衡以及数据的空间分布。

第 16 章 四叉树与 K-D 树¶