• 目錄

簡介

KD 樹又稱 K 維樹 (K-dimensional tree)，是一種可以對 K 維資料進行劃分的資料結構，可以看成二元搜尋樹的一種延伸，不斷的對空間中的維度做劃分，利用搜尋樹剪枝的特性縮短時間複雜度，主要應用在多維空間搜尋，例如最近鄰居搜索。

背景

以前在學資料結構的時候，學過使用二元搜尋樹將資料用大小區分來建樹，每個點代表著一筆資料，這個方法在資料只有一個維度的時候行的通，但當資料超過一個維度的時候就遇到困難，該怎麼對二維以上的陣列進行劃分。

想法

對於多維陣列，我們多了一個以上的維度，因此在劃分時沒有一個劃分依據，此時我們可以將所有資料統一使用其中一個維度進行劃分，這個動作在二維資料內相當於將空間劃分為兩個部分，得到兩個新的子空間，如果我們繼續對這兩個子空間進行上述劃分，又會得到新的子空間，重複以上過程直到每個子空間都不能再劃分為止。

<aside> 💡 相當於不斷的用超平面將 K 維空間切分，每個節點對應一個 K 維超矩形區域。

</aside>

以上就是建立 KD 樹的過程，上述過程中涉及到兩個重要的問題：

1. 每次選擇其中一個維度進行劃分時，應該選擇哪個維度進行劃分？
2. 在某個維度上的進行劃分時，應該選擇哪個節點進行劃分？

劃分方法

術語

• cell：KD 樹數據結構為把空間遞歸地劃分兩個不相交的超矩形（類似於超平面、超立方體的概念），每個超矩形所佔的空間即為一個 cell。
• bounding rectangle：包含數據集中所有點的最小超矩形。其範圍小於等於該節點對應 cell 的大小。
• aspect ratio：cells 中最長邊與最短邊的長度比，比值越大，數目 cell 越細長，反之，越肥胖。
• spread：數據集在某維度上最大值減最小值。即該維度上 bounding rectangle 對應邊的長度。