大量 point 資料結構 :
k-dimensional tree
摘要
| build | build | search | orthogonal | time | space | (ins/del) | range search -----------+-------------+-------------+-----------+-------------- kd-tree | O(NlogN) | O(N) | O(logN) | O(N1-1/D + K) range tree | O(Nlogᴰ⁻¹N) | O(Nlogᴰ⁻¹N) | O(logᴰN) | O(logᴰN + K)
k 維樹
大量儲存多維平面上的點,並且依照地緣關係來排序。常縮寫為 k-d tree 、 kd-tree 。以下分別介紹一維和二維的情形。
一維 kd-tree
1d-tree 的原理與 binary search tree 十分類似,但是長相卻有點不同。在 1d-tree 當中,資料全部集中在樹葉;得補一些數據到內部節點,才能做搜尋。
一維 kd-tree :建立
建立的方法,是把數線上的點分為左右兩等份,然後分別遞迴下去。習慣上是挑中位數位置的點作為分割點,分割點劃分於左側。
求分割點時,是使用時間為 O(N) 的求中位數演算法,而不是使用時間為 O(NlogN) 的排序演算法,才能達到理論上的時間複雜度。然而實際上排序演算法比較容易實作,效率也不錯。
時間複雜度 O(NlogN) ,空間複雜度 O(2N - 1) = O(N) 。
一維 kd-tree :插入、刪除、搜尋
插入、刪除、搜尋的方式跟 binary search tree 的概念完全相同,時間複雜度都是 O(logN) 。
一維 kd-tree :大範圍搜尋
有一個重要的應用,是找出一個區間裡面所有的點。概念上是以搜尋範圍的左、右邊界值,分別搜尋一次,途中順便遍歷符合搜尋範圍內的子樹。
真正在實作時,則是同時以搜尋範圍的左、右邊界值進行搜尋:甲、如果搜尋完全落在分割點的其中一側,那麼就依照二元搜尋樹的規則繼續搜尋;乙、如果搜尋範圍橫跨分割點,那麼左右子樹都要搜尋;丙、如果搜尋範圍包含一整條分割區段,就可以直接遍歷整棵子樹,也可以當作是乙的情況來處理。
時間複雜度 O(2logN + 2K-1) = O(logN + K) , K 為區間裡面的點數目。
延伸閱讀:另外一種建立一維 kd-tree 的方式
1d-tree 另外有一種獨特的建樹方式:先排序所有資料,需時 O(NlogN) ,然後再以 bottom-up 順序建立 1d-tree ,需時 O(2N - 1) = O(N) 。整體的時間複雜度仍相同。
讀者可能會想:既然要先排序,那乾脆就把資料放到陣列,排序完之後,直接二元搜尋不就好了,幹嘛需要 1d-tree 呢?你想的沒錯,一維的情況下,資料又不會變動時,的確沒有這個必要。
延伸閱讀:內部節點有兩種記錄方式
內部節點有兩種記錄方式。基本的方式是記錄分割點座標,這是仿照 binary search tree 的原理;進階的方式是記錄其下所有樹葉的數值範圍,實作起來會複雜一點。這兩種記錄方式也可以同時使用。
採用進階的方式有一個好處:可以允許樹葉當中有許多相同座標的點。如此一來,座標相同的點就能進行左右兩等份,閃避了分割點的二元搜尋規則。
一般來說, kd-tree 沒有必要使用進階的方式。在 range tree 當中,才有必要用到進階的方式。
二維 kd-tree
兩個維度依序作為等分的依據,輪流遞迴下去。
二維 kd-tree :建立
先以垂直線,把平面上的點分為左右兩等份,左右兩區域各自再以水平線,將平面上的點等分為上下兩等份。垂直、水平如此不斷輪流遞迴下去,直到每個區域都只剩一個點。
時間複雜度 O(NlogN) 。空間複雜度 O(2N - 1) = O(N) 。
二維 kd-tree :插入、刪除、搜尋
插入、刪除、搜尋的方式跟 binary search tree 的概念完全相同,時間複雜度都是 O(logN) 。
二維 kd-tree :大範圍搜尋
有一個重要的應用,是找出一個長方形範圍裡面所有的點:甲、如果搜尋範圍完全落在分割線的其中一側,那麼就依照二元搜尋樹的規則繼續搜尋;乙、如果搜尋範圍橫跨分割線,那麼左右子樹都要搜尋;丙、如果搜尋範圍包含一整塊分割區域,就可以直接遍歷整棵子樹,也可以當作是乙的情況來處理。
搜尋時,垂直方向最多遇到 O(sqrtN) 個區域,水平方向最多遇到 O(sqrtN) 個區域,時間複雜度 O(2sqrtN + 2K-1) = O(sqrtN + K) , K 為長方形裡面的點數目。
高維 kd-tree
建立時間為 O(NlogN) ,建立空間為 O(N) ,插入、刪除、搜尋的時間為 O(logN) ,搜尋 D 體形範圍的時間為 O(N1-1/D + K) 。
ICPC 6041
大量 point 資料結構 :
range tree
範圍樹
大量儲存多維平面上的點,並且依照地緣關係來排序,用途和「 k 維樹」一模一樣。
「範圍樹」的基本操作都比「 k 維樹」略遜一籌,但是「範圍樹」做大範圍搜尋時,竟神奇地比「 k 維樹」快上許多。以下分別介紹一維和二維的情形。
一維 range tree
就是一維 kd-tree 。
二維 range tree
一棵 X 座標為主的 1d-tree ,每一個內部節點都連繫到一棵 Y 座標為主的 1d-tree ,由內部節點所管轄的點所構成。
X 樹可能有 X 座標相同、 Y 座標不同的點; Y 樹可能有 Y 座標相同、 X 座標不同的點。因此,內部節點改為記錄其下所有樹葉的數值範圍,如此一來,座標相同的點就能進行左右兩等份。
二維 range tree :建立
甲、首先建立 X 樹;乙、於回溯時,使用 merge sort 將子樹的點重新依照 Y 座標排序;丙、同時,拿排序好的點,以 bottom-up 方式,建立 Y 樹。
X 樹的高度是 O(logN) ,樹根到樹葉的路徑長度是 O(logN) 。對於 X 樹的其中一個樹葉,只可能出現在 O(logN) 棵 Y 樹當中。可得空間複雜度 O(NlogN) 。
時間複雜度 O(NlogN) ,空間複雜度 O(NlogN) 。
二維 range tree :插入、刪除、搜尋
先以 X 座標搜尋 X 樹,沿途每一個內部節點,再以 Y 座標深入搜尋 Y 樹。
時間複雜度 O(log²N) 。
二維 range tree :大範圍搜尋
有一個重要的應用,是找出一個長方形範圍裡面所有的點。以長方形的左、右邊界值,分別搜尋 X 樹,找出在左、右邊界範圍內的所有子樹及樹葉,再以上、下邊界值,深入搜尋 Y 樹。
概念上可以解讀成:先過濾 X 座標,再過濾 Y 座標。
時間複雜度 O(log²N + K) , K 為長方形裡面的點數目。終於比 kd-tree 快!
高維 range tree
建立時間為 O(Nlogᴰ⁻¹N) ,建立空間為 O(Nlogᴰ⁻¹N) ,插入、刪除、搜尋的時間為 O(logᴰN) ,搜尋 D 體形範圍的時間為 O(logᴰN + K) 。
延伸閱讀: fractional cascading
當資料不會變動時,可以把最深維度的 1d-tree 改為陣列,就可以利用 fractional cascading 減少搜尋的時間,搜尋的時間可以除掉一個 logN 。
搜尋的時間變為 O(logᴰ⁻¹N) ,搜尋 D 體形範圍的時間變為 O(logᴰ⁻¹N + K) 。
ICPC 6045
大量 interval 資料結構 :
interval tree
區間樹
置放大量區間,並且進行排序的資料結構。
排序 2N 個區間端點,以中位數位置的端點作為分界線。樹根是橫跨兩側的區間,依照左端點排序;左子樹是位於左側的區間;右子樹是位於右側的區間。
空間 O(N) ,建立 O(NlogN) ,搜尋 O(logN + K) 。
另一種區間樹
平衡的 binary search tree ,以區間左端點作為鍵值。每個節點額外記錄其子樹所有區間的右邊界。
空間 O(N) ,建立 O(NlogN) ,搜尋 O(logN + K) 。
大量 interval 資料結構 :
segment tree
大量 shape 資料結構 :
binary space partitioning tree