BSP树作为多维搜索结构
空间搜索结构基于60年代和70年代在计算机科学中发明的相同思想，用于解决快速处理大量符号数据而不是几何数据（例如人名列表）的问题。发明了一种方法，首先通过根据字母对名称列表进行排序，然后将排序后的列表存储在数组中，就可以使用二进制搜索算法（而不是n / 2）来计算log2n操作中列表中是否已经有一些新名称在顺序搜索的帮助下所需的预期操作。这是一个很好的示例，它可以提取名称列表中现有的结构（字母顺序），并在后续操作（查找名称）中利用该结构来减少计算量。
但是，如果希望在保留排序列表的同时允许名称的添加和删除，则需要一种动态数据结构，即一个实现指针。这种数据结构最常见的例子之一就是二进制搜索树。
在二叉搜索树的情况下，将其实现为表示位于实线上的整数集，例如A = {1,2,5,6,7,9}。要计算树中是否已经存在数字/点，可以将点插入树中并遵循与包含该点的嵌套间隔序列相对应的路径。对于平衡树，此过程将消耗不超过O（log n）个步骤；因为事实上，我们执行了二进制搜索，但是执行的是树而不是数组。现在，树本身可以对搜索算法的一部分进行编码，因为它可以确定搜索进行的顺序。
现在，这使我们回到了分区树，它们被视为二叉搜索树的概括，即维度> 1（即多维）（在一维中，它们本质上是相同的）。实际上，可以将构建分区树想象为快速排序的几何版本。
更改（删除和插入）是通过合并树来实现的，类似于合并“合并排序”中的排序列表。
但是，由于点不会在任何大于1的维度上划分空间，因此必须实现超平面，而不是要细分的点。
超平面总是将一个区域细分或划分为两个半空间，而与尺寸无关。
以上是 BSP树作为多维搜索结构 的全部内容， 来源链接： utcz.com/z/340929.html
