- k-d tree教學投影片
- http://andrewd.ces.clemson.edu/courses/cpsc805/references/nearest_search.pdf
- https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/paska13.pdf
- 在二維空間的查找優化
- K-D Tree在信息学竞赛中的应用
- K-D tree的估价
- 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 感謝Morris大大的模板
- 構造
現在有一個point序列S[0~n-1]，每個point都包含一個序列d[0~kd-1]表示維度，S[i].d[j]表示第i個點的第j維。
節點的資料型別定義為node，裡面有l,r兩個指標分別指向左右兩顆子樹，還有一個point pid表示所存的point。
構造的過程是一個遞迴結構，大致代碼如下:
當前這個節點的k稱為分裂維度
- 查找
kd樹支援兩種查找法:
一、給定一個點p和一個數字k，求離p前k近的點有哪些
二、給定一個範圍，求範圍內有哪些點
兩種方法跟一般爆搜有點像，但是利用了kd樹可以做到有效的剪枝，有時候可以判斷被切分出來的範圍內有沒有機會存在前k近點或是在範圍內，直接看模板應該就懂了 - 刪除
模板裡沒有附刪除的code所以會寫在這裡。
首先如果找到要刪除的節點是葉節點直接刪除就好了；如果不是葉節點，假設現在這個點的分裂維度是k，就拿他右子樹第k維最小節點mi去替代他，接著遞迴刪除右子樹的mi；如果沒有右子樹，就拿他左子樹第k維最小節點mi去替代他，然後把左右子樹互換，接著遞迴刪除右子樹的mi。
找到要刪除的點用查找中的第一種方法就好了，這裡p=要刪除的點，k=1，查找的時候順便維護最近節點其位置與其對p的距離，若最近距離!=0則刪除失敗。
那對一個子樹找第k維最小節點呢?方法很簡單，也是遞迴定義的:
首先如果當前節點o的分裂維度剛好是第k維，則若o有右子樹的話答案必在o的右子樹，否則答案為o，如果o的分裂維度!=k，則遞迴搜尋左右子樹，把得到的答案和o自己進行比較，求最小。
接下來附上只有刪除操作的模板:
設N=size(root)
- 構造:
很明顯就是\(\ord{N \; log \; N}\)就不說了 - 查找:
已經有人證明了，假設現在的維度有k維，則查找的最差複雜度是\(\ord{N^{1-1/k}}\)
但是平均狀況下為\(\ord{log \; N}\) - 插入:
複雜度為\(\ord{樹的高度}\)，因為是套替罪羊樹，而且重構的時間是\(\ord{N \; log \; N}\)，所以單次插入的均攤時間複雜度是\(\ord{log \; N \; * \; log \; N}\) - 刪除:
有三個步驟需要分析，假設現在的維度有k維- findmin:
最多會遍歷\(\alpha^{(k-1)*(log_{\alpha}N)/k}=N^{1-1/k}\)個節點，所以是\(\ord{N^{1-1/k}}\)
但實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是最小值的子樹大小 - nearest:
就是查找操作，所以是\(\ord{N^{1-1/k}}\)
但因為是找相同點，可以優化code，所以實際操作量為\(N^{1-1/k}-n^{1-1/k}\)，n是相同點的子樹大小 - 刪除操作本身:
看code明顯就是重複findmin直到把刪除的點變成葉節點為止，會感覺做了很多操作，但是我們發現把所有操作加起來後會=\(\ord{N^{1-1/k}}\)
設\(o_1,o_2,...,o_d\)=findmin(root)找到的點,findmin(\(o_1\))找到的點,\(...\),要刪除的葉節點，\(n_1,n_2,...,n_d\)=findmin(root)找到的點的子樹大小,findmin(\(o_1\))找到的點的子樹大小,findmin(\(o_2\))找到的點的子樹大小,\(...\),要刪除的葉節點的子樹大小，\(d\)為樹的高度
複雜度為:
$$ N^{1-1/k}-n1^{1-1/k}+n1^{1-1/k}-n2^{1-1/k}+n2^{1-1/k}...-nd^{1-1/k}=\ord{N^{1-1/k}} $$
- findmin:
這樣查找時回傳的就是歐基里德距離的平方
以下附只有插入操作的模板:
以下附支援插入刪除的模板:
模板的使用方法請參考:
