BSP樹作為多維搜尋結構

空間搜尋結構基於計算機科學在60年代和70年代為快速處理大型符號資料（而不是幾何資料，例如人員姓名列表）而發明的一些相同思想。它首先根據字母表對姓名列表進行排序，並將排序後的列表儲存在陣列中，然後可以使用二分查詢演算法在log2n次操作中計算某個新名稱是否已在列表中，而不是順序查詢所需的n/2次預期操作。這是一個很好的例子，它提取了姓名列表中存在的結構（字母順序），並在後續操作（查詢姓名）中利用該結構來減少計算。

但是，如果希望在保持排序列表的同時允許新增和刪除名稱，則需要動態資料結構，即實現指標的結構。這種資料結構中最常見的例子之一就是二叉搜尋樹。

在二叉搜尋樹的情況下，它被用來表示一組整數，例如A = {1, 2, 5, 6, 7, 9}位於實線上。為了計算某個數字/點是否已在樹中，可以將該點插入到樹中，並遵循與包含該點的巢狀區間序列對應的路徑。對於平衡樹，此過程最多消耗O(log n)步；實際上，我們已經執行了二分查詢，但是它實現的是樹而不是陣列。現在，樹本身能夠編碼搜尋演算法的一部分，因為它決定了搜尋前進的順序。

這現在將我們帶回到劃分樹，它們被視為二叉搜尋樹到大於1維（即多維）的泛化（在一維中，它們本質上是相同的）。事實上，構建劃分樹可以想象成快速排序的幾何版本。

更改（刪除和插入）是透過合併樹來實現的，類似於在歸併排序中合併排序列表。

但是，由於點不會劃分任何大於1維的空間，我們必須實現超平面而不是點來進行細分。

無論維度如何，超平面總是將區域細分為兩個半空間。

Arnab Chakraborty

更新於：2020年1月8日

瀏覽量：133

開啟你的職業生涯

完成課程獲得認證

開始學習