摘要

           | 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(N^1-1/D + K) 。

ICPC 6041

範圍樹

大量儲存多維平面上的點，並且依照地緣關係來排序，用途和「 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

區間樹

置放大量區間，並且進行排序的資料結構。

排序 2N 個區間端點，以中位數位置的端點作為分界線。樹根是橫跨兩側的區間，依照左端點排序；左子樹是位於左側的區間；右子樹是位於右側的區間。

空間 O(N) ，建立 O(NlogN) ，搜尋 O(logN + K) 。

另一種區間樹

平衡的 binary search tree ，以區間左端點作為鍵值。每個節點額外記錄其子樹所有區間的右邊界。

空間 O(N) ，建立 O(NlogN) ，搜尋 O(logN + K) 。

區段樹

置放大量區間，並且進行排序的資料結構。

排序 2N 個區間端點，將數線切成最多 2N-1 個區段，一個區段對應一個樹葉。

top-down 觀點：標記區間涵蓋的子樹，只標記子樹樹根。

bottom-up 觀點：標記區間涵蓋的樹葉，往上合併標記。

儲存一個區間，每一層最多標記兩個節點，整棵樹最多標記 2logN 個節點。儲存 N 個區間，空間複雜度 O(NlogN) 。

空間 O(NlogN) ，建立 O(NlogN) ，搜尋 O(logN + K) 。

UVa 10535 ICPC 4108

binary space partitioning tree

大量儲存多維空間裡的圖形，並且依照地緣關係來排序。常縮寫為 BSP tree 。

概念仿照 kd-tree 。任取一筆資料，作為分界處，將空間劃分成左右兩區，將剩餘資料分為左右兩堆，遞迴分割下去。橫跨分界處的資料，必須切開，成為左右兩份。

三維空間，資料是三角形：隨便抓一個三角形，作為分界面，將空間劃分成左右兩區，並將其餘三角形們劃分成左右兩堆，遞迴分割下去。

二維平面，資料是線段：仿前。

二維平面、三維空間，資料是點：即是 kd-tree 。

UVa 1542 ICPC 2105