算法技术手册（原书第2 版）

270

｜

第

10

章

൶ᇘࡀఇ

图 10-3：使用基于区域划分的四叉树

基于点的四叉树

四叉树将笛卡儿平面

2

k

×

2

k

的空间直接映射为二叉树结构，其中每个结点最多可以

存储

4

个点。如果将某个点加入一个未被切分的区域中，那么该区域会被继续切分

为

4

个子区域，其中每个子区域大小为父结点的

1/4

。如果某个象限中不存在任何点，

那么该象限就没有子结点。因此，树的形状依赖于点加入到四叉树中的顺序。

本章主要关注基于点的四叉树。图

10-4

所示为包含

13

个点的

256

×

256

区域的四叉树示

例，图中右侧所示即为四叉树的结构。注意：根结点的东南象限没有任何点，因此根结

点仅有

3

个子结点。还 应注意的是，各种不同的区域细分是以加入四叉树中的点为基础的。

10.4.3 R 树

R

树

是一个树状结构，其中每个结点最多包含

M

个指向子结点的连接。所有实际信息均

存储在叶结点中，每个叶结点最多可以存储

M

个不同的矩形。图

10-5

展示了

M

= 4

的

R

树，

其中共有

6

个矩形插入树中（标号为

1

、

2

、

3

、

4

、

5

、

6

），图中右侧所示即为构建出的

R

树，其中每个内部结点代表了实际矩形中的不同矩形区域。