BSP树作为多维搜索结构

空间搜索结构基于计算机科学在60年代和70年代为快速处理大型符号数据（而不是几何数据，例如人员姓名列表）而发明的一些相同思想。它首先根据字母表对姓名列表进行排序，并将排序后的列表存储在数组中，然后可以使用二分查找算法在log2n次操作中计算某个新名称是否已在列表中，而不是顺序查找所需的n/2次预期操作。这是一个很好的例子，它提取了姓名列表中存在的结构（字母顺序），并在后续操作（查找姓名）中利用该结构来减少计算。

但是，如果希望在保持排序列表的同时允许添加和删除名称，则需要动态数据结构，即实现指针的结构。这种数据结构中最常见的例子之一就是二叉搜索树。

在二叉搜索树的情况下，它被用来表示一组整数，例如A = {1, 2, 5, 6, 7, 9}位于实线上。为了计算某个数字/点是否已在树中，可以将该点插入到树中，并遵循与包含该点的嵌套区间序列对应的路径。对于平衡树，此过程最多消耗O(log n)步；实际上，我们已经执行了二分查找，但是它实现的是树而不是数组。现在，树本身能够编码搜索算法的一部分，因为它决定了搜索前进的顺序。

这现在将我们带回到划分树，它们被视为二叉搜索树到大于1维（即多维）的泛化（在一维中，它们本质上是相同的）。事实上，构建划分树可以想象成快速排序的几何版本。

更改（删除和插入）是通过合并树来实现的，类似于在归并排序中合并排序列表。

但是，由于点不会划分任何大于1维的空间，我们必须实现超平面而不是点来进行细分。

无论维度如何，超平面总是将区域细分为两个半空间。

更新于：2020年1月8日

浏览量：133

开启你的职业生涯

完成课程获得认证

开始学习
广告