k-d樹

k-d 樹
類型	多維 二叉搜尋樹
發明時間	1975年
發明者	喬恩·本特利
用大O符號表示的時間複雜度
演算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ $O(n)$ 插入 $O(\log n)$ $O(n)$ 刪除 $O(\log n)$ $O(n)$

一個三維k-d樹。第一次劃分（紅色）把根節點（白色）劃分成兩個節點，然後它們分別再次被劃分（綠色）為兩個子節點。最後這四個子節點的每一個都被劃分（藍色）為兩個子節點。因為沒有更進一步的劃分，最後得到的八個節點稱為葉子節點。

在電腦科學里，k-d樹（k-維樹的縮寫）是在k維歐幾里德空間組織點的數據結構。k-d樹可以使用在多種應用場合，如多維鍵值搜尋（例：範圍搜尋及最鄰近搜尋）。k-d樹是空間二分樹的一種特殊情況。

簡介

k-d樹是每個葉子節點都為k維點的二叉樹。所有非葉子節點可以視作用一個超平面把空間分割成兩個半空間。節點左邊的子樹代表在超平面左邊的點，節點右邊的子樹代表在超平面右邊的點。選擇超平面的方法如下：每個節點都與k維中垂直於超平面的那一維有關。因此，如果選擇按照x軸劃分，所有x值小於指定值的節點都會出現在左子樹，所有x值大於指定值的節點都會出現在右子樹。這樣，超平面可以用該x值來確定，其法線為x軸的單位向量。

k-d樹的運算

建立k-d樹

有很多種方法可以選擇軸垂直分割面（axis-aligned splitting planes），所以有很多種建立k-d樹的方法。 最典型的方法如下：

• 隨着樹的深度輪流選擇軸當作分割面。（例如：在三維空間中根節點是 x 軸垂直分割面，其子節點皆為 y 軸垂直分割面，其孫節點皆為 z 軸垂直分割面，其曾孫節點則皆為 x 軸垂直分割面，依此類推。）
• 點由垂直分割面之軸座標的中位數區分並放入子樹

這個方法產生一個平衡的k-d樹。每個葉節點的高度都十分接近。然而，平衡的樹不一定對每個應用都是最佳的。

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;
        
    // Sort point list and choose median as pivot element
    select median by axis from pointList;
        
    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

平衡

在動態插入刪除點且不允許預處理插入操作的情況下，一種平衡的方法是使用類似替罪羊樹的方法重構整棵樹。

最鄰近搜尋

最鄰近搜尋用來找出在樹中與輸入點最接近的點。

k-d樹最鄰近搜尋的過程如下：

1. 從根節點開始，遞歸的往下移。往左還是往右的決定方法與插入元素的方法一樣(如果輸入點在分區面的左邊則進入左子節點，在右邊則進入右子節點)。
2. 一旦移動到葉節點，將該節點當作"目前最佳點"。
3. 解開遞歸，並對每個經過的節點執行下列步驟：
   1. 如果目前所在點比目前最佳點更靠近輸入點，則將其變為目前最佳點。
   2. 檢查另一邊子樹有沒有更近的點，如果有則從該節點往下找
4. 當根節點搜尋完畢後完成最鄰近搜尋

處理高維數據

維數災難讓大部分的搜尋演算法在高維情況下都顯得花俏且不實用。 同樣的，在高維空間中，k-d樹也不能做很高效的最鄰近搜尋。一般的準則是：在k維情況下，數據點數目N應當遠遠大於$2^{k}$時，k-d樹的最鄰近搜尋才可以很好的發揮其作用。不然的話，大部分的點都會被查詢，最終演算法效率也不會比全體查詢一遍要好到哪裏去。另外，如果只是需要一個足夠快，且不必最佳的結果，那麼可以考慮使用近似鄰近查詢的方法。

外部連結

• libkdtree++, an open-source STL-like implementation of k-d trees in C++.
• A tutorial on KD Trees
• A C++ implementation of k-d trees for 3D point clouds, part of the Mobile Robot Programming Toolkit (MRPT)
• kdtree （頁面存檔備份，存於互聯網檔案館） A simple C library for working with KD-Trees
• K-D Tree Demo, Java applet （頁面存檔備份，存於互聯網檔案館）
• libANN （頁面存檔備份，存於互聯網檔案館） Approximate Nearest Neighbour Library includes a k-d tree implementation
• Caltech Large Scale Image Search Toolbox: a Matlab toolbox implementing randomized k-d tree for fast approximate nearest neighbour search, in addition to LSH, Hierarchical K-Means, and Inverted File search algorithms.