日月卦長的模板庫: [ dynamic kd tree ] 動態kd樹模板

參考資料:

kd樹的資料在網路上其實滿多的，但很多code效率不高或是功能不全，所以這邊稍微講解一下kd樹基本的一些操作

構造
現在有一個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維
1. 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是最小值的子樹大小
2. nearest:
  就是查找操作，所以是$\ord{N^{1-1/k}}$
  但因為是找相同點，可以優化code，所以實際操作量為$N^{1-1/k}-n^{1-1/k}$，n是相同點的子樹大小
3. 刪除操作本身:
  看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}} $$

模板裡的code找的是曼哈頓距離，如果要找歐基里德距離只需要修改point裡的dist跟kd tree裡的heuristic即可，以下提供修改方法:
這樣查找時回傳的就是歐基里德距離的平方

以下附只有插入操作的模板:

以下附支援插入刪除的模板:
模板的使用方法請參考:

日月卦長的模板庫

2016年2月25日星期四

[ dynamic kd tree ] 動態kd樹模板

日月卦長的解題紀錄 [ IOICAMP2016 ] 動態曼哈頓最短距離

1 則留言:

2016年2月25日 星期四

[ dynamic kd tree ] 動態kd樹模板

日月卦長的解題紀錄 [ IOICAMP2016 ] 動態曼哈頓最短距離

1 則留言:

2016年2月25日星期四