k-d樹
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目沒有列出任何參考或來源。 (2024年2月14日) |
k-d 樹 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 多維 二元搜尋樹 | ||||||||||||||||||||
發明時間 | 1975年 | ||||||||||||||||||||
發明者 | 喬恩·本特利 | ||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||
|
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/250px-3dtree.png)
在電腦科學里,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樹最鄰近搜尋的過程如下:
- 從根節點開始,遞迴的往下移。往左還是往右的決定方法與插入元素的方法一樣(如果輸入點在分割區面的左邊則進入左子節點,在右邊則進入右子節點)。
- 一旦移動到葉節點,將該節點當作"目前最佳點"。
- 解開遞迴,並對每個經過的節點執行下列步驟:
- 如果目前所在點比目前最佳點更靠近輸入點,則將其變為目前最佳點。
- 檢查另一邊子樹有沒有更近的點,如果有則從該節點往下找
- 當根節點搜尋完畢後完成最鄰近搜尋
處理高維資料
維數災難讓大部分的搜尋演算法在高維情況下都顯得花俏且不實用。 同樣的,在高維空間中,k-d樹也不能做很高效的最鄰近搜尋。一般的準則是:在k維情況下,資料點數目N應當遠遠大於時,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.
|