15.4.1. PR 四叉树¶

在 点区域四叉树 （以下简称为 PR 四叉树）中，每个结点要么恰好有四个孩子，要么是叶结点。也就是说，PR 四叉树在形状上是一棵满的四路分支（4 叉）树。 PR 四叉树通过将包含数据点的区域分解为四个相等的象限、子象限，依此类推，直到没有叶结点包含超过一个点，来表示二维空间中的数据点集合。换句话说，如果一个区域包含零个或一个数据点，那么它由一棵只包含单个叶结点的 PR 四叉树表示。如果该区域包含多于一个数据点，那么该区域被分割成四个相等的象限。相应的 PR 四叉树包含一个内部结点和四个子树，每个子树表示该区域的一个象限，而这个象限又可能被分割成子象限。 PR 四叉树的每个内部结点表示二维区域的一次分割。该区域的四个象限（或等价地，对应的子树）按顺序命名为西北（NW）、东北（NE）、西南（SW）和东南（SE）。每个包含多于一个点的象限又将被递归地划分为子象限，直到对应 PR 四叉树的每个叶结点至多包含一个点。

例如，考虑图 15.4.1 (a) 的区域以及图 15.4.1 (b) 中对应的 PR 四叉树。分解过程要求固定的键范围。在此示例中，假设区域的大小为 \(128 \times 128\)。注意，PR 四叉树的内部结点仅用于指示区域的分解；内部结点不存储数据记录。由于分解线是预先确定的（即使用键空间分解），PR 四叉树是一种字典树。

在 PR 四叉树中查找与点 \(Q\) 匹配的记录非常直接。从根开始，我们不断分支到包含 \(Q\) 的象限，直到查找到达叶结点。如果根是叶结点，那么只需检查该结点的数据记录是否与点 \(Q\) 匹配。如果根是内部结点，则转入包含查找坐标的孩子。例如，图 15.4.1 的西北象限包含 \(x\) 和 \(y\) 值都在 0 到 63 范围内的点。东北象限包含 \(x\) 值在 64 到 127 范围、\(y\) 值在 0 到 63 范围内的点。如果根的孩子是叶结点，那么检查该孩子看 \(Q\) 是否已被找到。如果该孩子是另一个内部结点，查找过程继续沿树向下进行，直到找到叶结点。如果这个叶结点存储的记录位置与 \(Q\) 匹配，那么查询成功；否则 \(Q\) 不在该树中。

下面是一个 PR 四叉树的可视化演示，应该能帮助你理解如何插入一个点或删除一个点。

注意，当一个结点中有多个点时，树并没有特别的理由一定要分裂。这种分裂标准可以是实现者想要的任何条件。

下面是 PR 四叉树的交互式可视化。你可以通过添加或删除点来构建自己的示例。看看你是否能创建一棵与本页顶部图片形状相同的树。

下面的交互式可视化允许你在需要时使用不同的分裂值。如果树与页面顶部的图具有相同的点，但允许一个结点包含两个点，那么树会是什么样子？

使用 PR 四叉树可以很容易地执行区域查找。要定位查询点 \(Q\) 半径 \(r\) 范围内的所有点，从根开始。如果根是空的叶结点，那么没有找到数据点。如果根是包含数据记录的叶结点，那么检查该数据点的位置，以确定它是否落在该圆内。如果根是内部结点，那么递归执行该过程，但 只 对那些包含查找圆部分内容的子树进行。

现在考虑 PR 四叉树的结构如何影响其结点表示的设计。 PR 四叉树实际上是一种 字典树。内部结点的分解发生在中点，与数据点实际落在何处无关。数据点的位置确实决定了结点 是否 发生分解，但不决定该结点的分解 发生在哪里 。 PR 四叉树的内部结点与叶结点非常不同，因为内部结点有孩子（叶结点没有），而叶结点有数据字段（内部结点没有）。因此，内部结点很可能应该与叶结点采用不同的表示方式。最后，还有一点：约有半数的叶结点不包含数据字段。

另一个要考虑的问题是：遍历 PR 四叉树的例程如何获得当前 PR 四叉树结点所表示的正方形的坐标？一种可能是在每个结点中存储其空间描述（例如左上角和宽度）。然而，这将占用大量空间—可能多达存储数据记录所需的空间，具体取决于存储的信息。

另一种可能是在进行递归调用时传入坐标。例如，考虑查找过程。最初，查找访问树的根结点，其原点是 (0, 0)，宽度是所覆盖空间的完整大小。当访问适当的孩子时，查找例程很容易确定孩子的原点，而正方形的宽度只是父结点的一半。传入结点的大小和位置信息不仅节省了大量空间，而且避免在结点中存储此类信息还能为空叶结点做出好的设计选择，如下所述。

我们应该如何表示空叶结点？平均而言，PR 四叉树中约有一半叶结点是空的（即不存储数据点）。一种实现选择是在内部结点中使用 NULL 指针表示空结点。这将解决空间需求过大的问题。一个副作用是使用 NULL 指针要求 PR 四叉树的处理方法理解这个约定。换句话说，你破坏了结点的封装，因为树现在必须知道结点是如何实现的。对于这个特定的应用来说这并不太糟糕，因为结点类可以被视为树类的私有成员，在这种情况下结点实现对任何外部对象完全不可见。然而，如果有其他合理的选择，这种做法就不可取了。

幸运的是，有一个好的替代方案。它被称为 享元 设计模式。在 PR 四叉树中，享元是一个单一的、在所有需要空叶结点的地方都被复用的空叶结点。你只需让所有具有空叶子孩子的内部结点都指向同一个结点对象。这个结点对象在程序开始时创建一次，并且永远不会被删除。结点类从指针值识别出正在访问享元，并据此行动。

注意，使用享元设计模式时，你 不能 在结点中存储坐标。这是内在与外在状态概念的一个例子。对象的内在状态是存储在对象本身中的状态信息。如果在结点对象中存储坐标，那些坐标就是内在状态。外在状态是存储在环境其他地方的关于对象的状态信息，例如存储在全局变量中或传递给方法。如果处理树的递归调用传入当前结点的坐标，那么这些坐标就是外在状态。一个享元只能在其内在状态中 仅 存储对所有享元实例都准确的信息。坐标显然不符合条件，因为每个空的叶结点都有自己的位置。因此，如果你想使用享元，就必须传入坐标。

另一个设计选择是：谁控制工作，结点类还是树类？例如，在插入操作中，你可以让树类控制沿树向下的流程，查看（查询）结点以确定它们的类型并据此作出反应。这是 BST 实现使用的典型方法。另一种方法是由结点类来完成工作。也就是说，为结点定义插入方法。如果结点是内部结点，它把城市记录传给适当的孩子（递归地）。如果结点是享元，它用一个新的叶结点替换自己。如果结点是满结点，它用一个子树替换自己。这是 组合设计模式 的一个例子。如果使用 NULL 指针来表示空叶结点，组合设计将很难实现。事实证明，使用组合设计时，PR 四叉树的插入和删除方法更容易实现。