3.1. PR 四叉树¶

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

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

在 PR 四叉树中查找与点 \(Q\) 匹配的记录非常 直接。 从根开始，我们不断分支到包含 \(Q\) 的象限，直到查找到达叶结点。 如果根是叶结点，那么只需检查该结点的数据 记录是否与点 \(Q\) 匹配。 如果根是内部结点，则转入包含 查找坐标的孩子。 例如，图 18.3.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 四叉树的插入和删除方法更容易实现。