檢視 K-d樹的原始碼

佇咧電腦科學里，'''_ k _-d 樹'''（'''k-維樹'''的縮寫）是佇咧 _ k _ 維歐幾里德空間組織點的資料結構。_ k _-d 樹仔會使用佇濟種應用的場合，親像加維鍵值搜揣（例：範圍搜揣著最近搜揣）。 _ k _-d 樹仔是空間二分樹仔（binary space partitioning）的一種特殊情況。

==簡介==

_ 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 + 一 ) ;
node . rightChild  :=kdtree ( points'''in'''pointList'''after'''median , depth + 一 ) ;
'''return'''node ;
}
` ` `

===插一个元素===

===共元素徙掉===

===做平衡===

佇動態插入去刪除點閣無允准預處理插入去操作的情況之下，一種平衡的方法是使用類似替罪羊樹的方法重構規欉樹仔。

===最近搜揣===

最近搜揣用來揣出佇樹仔內佮輸入點上倚近的點。

'''k'''-d 樹仔最近咧搜揣的過程如下：

一 . 對根節點開始，遞迴的落去下跤移。往倒爿往爿的決定方法佮插入元素的方法仝款 ( 若輸入點佇分割區面的倒爿則進入倒手節點，佇正爿進入正子節點 )。
二 . 一旦徙振動到葉節點，該當做皮 " 目前最佳點 "。
三 . 解開遞迴，而且對每一个經過的節點來執行列步：
一 . 若目前所在咧點比目前最佳點閣較倚近輸入點，著欲變做目前最佳點。
二 . 檢查另外一爿的樹仔敢有閣較近的點，若有則對該節點鬥陣揣四 . 當根節點揣好勢了後完成最鄰近搜揣



===處理高維資料===

維數災難予大部份的搜揣演算法佇高維的情形下攏顯得花趣味無實用。按呢仝款，佇高維空間內底，k-d 樹仔嘛袂當做足大效的最近搜揣。一般的準則是講：佇咧 k 維持情形下，資料點數目 N 應當遠遠大於 $ 二 ^ { 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 三 D 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 .

[[分類: 待校正]]