18.5. 二叉空间分割树（Bintree）¶
18.5.1. 二叉空间分割树¶
这个模块展示了一个在两个或多个维度中存储点数据的空间数据结构，称为 二叉空间分割树 。二叉空间分割树是 BST 向多维空间的自然扩展。二叉空间分割树在两个重要方面与 BST 不同。首先，作为多维数据结构，在树的每个层次上，二叉空间分割树 根据与该层次相关的特定查找键做出分支决策，称为 判别符 。其分割决策在各个键维度之间交替进行（一次只在一条维度上分割是二叉空间分割树与 PR 四叉树 的区别）。另一个与 BST 不同的区别是，二叉空间分割树使用的是称为 图像空间分解 的东西，因此是 字典树 的一种形式。图像空间分解将键空间分为相等的两半，而不是在所存储对象的键值处分割。（使用图像空间分解是二叉空间分割树与 kd 树 的区别，后者在数据点的位置上分割。）
理论上，二叉空间分割树可用于统一任意一组键的查找，例如名称和邮政编码。但在实践中，它几乎总是用于支持多维坐标上的查找，例如二维或三维空间中的位置。
我们将第 \(i\) 层的判别器定义为 \(i \bmod k\)，其中 \(k\) 为维度数。例如，假设我们按 \(xy\) 坐标存储数据。在这种情况下，\(k\) 为 2（有两个维度）， \(x\) 坐标字段被任意指定为键 0， \(y\) 坐标字段被指定为键 1。在每一层，判别器在 \(x\) 和 \(y\) 之间交替。因此，第 0 层（根）的结点 \(N\) 将用垂直分割线把整个世界分成两半。 \(x\) 坐标在下半部分的记录位于分割线的左侧，因而在左子树中。 \(x\) 坐标在上半部分的记录位于分割线的右侧，因而在右子树中。在此阶段，\(y\) 坐标值不起任何作用。
在第 1 层，\(y\) 坐标成为判别器。换句话说，世界左半部分将被水平地一分为二（如有必要）。
二叉空间分割树 中的叶结点可以为空，也可以包含一个数据点（此时称为满结点）。每当一个点要被插入到已经包含一个点的叶结点时，就会发生分裂。
在二叉空间分割树中查找具有指定 \(xy\) 坐标的记录就像查找 BST 一样，只是二叉空间分割树的每一层都与一个特定的判别器相关联。如果查找过程到达一个 null 指针，那么该点不在树中。
下面是二叉空间分割树的可视化演示，展示了插入一个点和删除一个点是如何工作的。
下面是用于练习的二叉空间分割树交互式可视化。
假设我们想打印出所有在给定点 \(P\) 的某一距离 \(d\) 之内的记录列表。我们将使用欧几里得距离，即点 \(P\) 被定义为在点 \(N\) 的距离 \(d\) 之内，如果 \(\sqrt{(P_x - N_x)^2 + (P_y - N_y)^2} \leq d\). [1]
查找通过一种"有向"遍历进行。当我们访问树中的一个结点时，只有当查找圆的包围盒与结点的包围盒相交时才继续。如果不相交，我们停止并返回。如果它与内部结点相交，我们访问该结点的孩子。如果是叶结点，那么我们询问其中包含的数据点是否在查找点的距离 \(d\) 之内。在平均情况下，区域查询期间必须访问的结点数量与落在查询圆内的数据记录数量成线性关系。
18.5.1.1. 实现考虑（Implementation Concerns）¶
现在让我们考虑二叉空间分割树的结构如何影响其结点表示的设计。二叉空间分割树 实际上是一种 字典树。这意味着内部结点的分解发生在中点，与数据点实际落在何处无关。数据点的位置确实决定了结点 是否 发生分解，但不决定该结点的分解 发生在哪里 。二叉空间分割树 的内部结点与叶结点非常不同，因为内部结点有孩子（叶结点没有），而叶结点有数据字段（内部结点没有）。因此，内部结点很可能应该与叶结点采用不同的表示方式。最后，还有一点：约有半数的叶结点不包含数据字段。
另一个要考虑的问题是：遍历二叉空间分割树的例程如何获得当前二叉空间分割树结点所表示的矩形的坐标？一种可能是在每个结点中存储其空间描述（例如左上角和宽度）。然而，这将占用大量空间—可能多达存储数据记录所需的空间，具体取决于存储的信息。
另一种可能是在进行递归调用时传入坐标。例如，考虑查找过程。最初，查找访问树的根结点，其左上角定义为 (0, 0)，宽度和高度是所覆盖空间的完整大小。当访问适当的孩子时，查找例程很容易确定孩子的原点，而判别器维度的长度正好是父结点的一半。传入结点的大小和位置信息不仅节省了大量空间，而且避免在结点中存储此类信息还能为空叶结点做出好的设计选择，如下所述。
我们应该如何表示空叶结点？平均而言，二叉空间分割树 中约有一半叶结点是空的（即不存储数据点）。一种实现选择是在内部结点中使用 null 指针表示空结点。这将解决空间需求过大的问题。一个副作用是使用 null 指针要求二叉空间分割树 的处理方法理解这个约定。换句话说，你破坏了结点的封装，因为树现在必须知道结点是如何实现的。对于这个特定的应用来说这并不太糟糕，因为结点类可以被视为树类的私有成员，在这种情况下结点实现对外界完全不可见。然而，如果有其他合理的选择，这种做法就不可取了。
幸运的是，有一个好的替代方案。它被称为享元设计模式。在二叉空间分割树中，享元是一个单一的、在所有需要空叶结点的地方都被复用的空叶结点。你只需让所有具有空叶子孩子的内部结点都指向同一个结点对象。这个结点对象在程序开始时创建一次，并且永远不会被删除。结点类从指针值识别出正在访问享元，并据此行动。
注意，使用享元设计模式时，你 不能 在结点中存储坐标。这是内在与外在状态概念的一个例子。对象的内在状态是存储在对象本身中的状态信息。如果在结点对象中存储坐标，那些坐标就是内在状态。外在状态是存储在环境其他地方的关于对象的状态信息，例如存储在全局变量中或传递给方法。如果处理树的递归调用传入当前结点的坐标，那么这些坐标就是外在状态。一个享元只能在其内在状态中 仅 存储对所有享元实例都准确的信息。坐标显然不符合条件，因为每个空的叶结点都有自己的位置。因此，如果你想使用享元，就必须传入坐标。
另一个设计选择是：谁控制工作，结点 类还是树类？ 例如，在插入操作中，你可以让树类 控制沿树向下的流程，查看（查询）结点以确定 它们的类型并据此作出反应。 这是典型 BST 实现采用的方法。 另一种方法是由结点类来完成工作。 也就是说，为结点定义插入方法。 如果结点是内部结点，它把城市记录传给适当的 孩子（递归地）。 如果结点是享元，它用一个新的叶结点替换自己 （通过返回 this）。 如果结点是满结点，它用（返回）一个子树替换自己。 这是 组合设计模式（Composite design pattern） 的一个例子。 如果使用空指针来表示空叶结点，组合设计将很难实现， 这也是为此目的使用享元的一个原因。 那么在实现插入和删除方法时， 使用组合设计比树控制方法更容易。
