在此之前我們探討過如何達到add, get, contain, delete等操作的資料結構，這章節要來談談range search的操作：

// Suppose we have a Set that will contain nth T type elements.
// {1, 4, 5, 6, 9, 11, 14, 17, 20}
select(int i) -> find ith smallest item.
ex: 
select(0) -> 1
select(3) -> 6

rank(T t) -> find t item's rank in the set.
ex:
rank(1) -> 0
rank(6) -> 3

subSet(T from, T to) -> find all items between from & to.
ex:
subSet(4, 9) -> {4, 5, 6, 9}
subSet(3, 12) -> {4, 5, 6, 9, 11}
subSet(12, 13) -> {}

nearest(T x) -> the item closest to x
ex:
nearest(6) -> 6
nearest(8) -> 9
nearest(10) -> 9 or 11

其實就跟get類似，我們只要多紀錄目標與當前node的距離就好了：

而其他select, rank, subSet也可以用類似的概念做到。

在此之前我們探討的功能都只針對一維的資料來進行，也就是每個元素都可以很明確地做到comparable，2一定大於1，zebra一定大於apple等等，所以接下來我們要探討的問題先鎖定在如何在二維中去找出nearest的做法。

下圖的範例是我們在宇宙中有這些黃點，我們要找出最靠近那批漂浮在宇宙中的馬的黃點：

我們有辦法建立二維的tree嗎? 試試根據x軸或y軸為基準來建立，就會如下圖所示：

如果如下圖範例，我們想找到x軸小於-1.5的node，我們其實可以不用走遍所有的node來確認，因為BST的結構，我們根本就不用去找A點右側的那串，因為A點本身的-1就已經大於-1.5了。這個判斷的行為我們稱為Pruning，在中文裡這個字是修剪樹枝的那個修剪。

可是這樣只能限於x軸的判斷，好像還是不夠周全，所以接著我們來介紹QuadTree。

Quad取自於quadratic，四邊形，代表tree會有四個面向來進行展開，在二維中就是四個方位：

以下我們來實際用一個範例感受Quadtree的運作，假設我們想找出下圖綠色框框中包含了哪些節點，該如何進行呢？一個關鍵的概念就是不斷去prune不在目標方位上的點，所以以下面的範例而言，我們就可以prune掉NW, SE, SW了：

如下圖由root A出發，並prune掉非目標方向的方位：

所以下一個點來到B，並判斷B是否在綠框中？沒錯，所以加入results中：

接著要來看我們之後要探索的方向有哪些？發現四個方位都在綠框中，所以四個方向等等都要探索：

首先探索NW：

再來換NE：

再來SE：

再來是SW，SW方向上就進行到點C了：

點C判斷完後，再來看要從哪個方向探索，發現只有NE在綠框中：

可是NE方向上沒有其他點了，故結束：

除了QuadTree可以處理二維資料外，還有另一種結構可以進行，就是k-d Tree。

k-d Tree其概念就是每一層判斷大小的基準會不斷交替x軸與y軸，比如第一層根據y軸判斷，那下一層會依據x軸判斷，不斷反覆：

我們來看一個nearest的範例，我們想找到跟目標點(1, 7)最接近的點是誰？

從root A出發，A與目標的距離為4.5

紀錄完距離後，接著往下一個點進行，該從哪個點開始呢？先從靠近目標的開始，所以從左半端先：

點E與目標的距離更好，於是更新best result，接著來看看該從哪個方向探索？先往靠近目標的來，所以是往上：

但點E上方沒有其他點了，故結束探索。接著是個關鍵的問題，我們有必要探索點E的下方嗎？有沒有可能存在更近的點？

答案是有可能！如果有存在點的x方向與目標更近，就有可能有比點E更靠近了，所以我們需要繼續探索這個方向：

可惜這邊沒有其他點存在：

再來回到root，右側有可能存在更靠近的點嗎？確實有可能！所以我們繼續探索右側：

右側第一個點是點B，其距離沒有比當前best result好，故跳過。接著往靠近目標點的方向探索：

到點C，距離也沒有當前的好，繼續往靠近目標點方向探索：

到點D，也沒更靠近，再繼續往靠近目標點方向探索：

沒有其他點了！

接下來思考，我們有必要往點D的下方探索嗎？會發現沒必要，因為那個方向上不可能存在比點E更靠近的距離，所以就可以prune掉這個方向：

在來回到點C，點C右側有可能有更靠近的點嗎？沒可能，所以也可以prune掉：

回到點B，點B下方會有更靠近的點嗎？沒可能，所以也prune掉：

然後就回到點A，就結束了～所有good side跟bad side的可能性都探索完了。

我們回到一開始宇宙馬的問題，除了利用quad tree來進行range search外，我們也可以用另一個想法進行，假設整個宇宙我們切分成以下16的區域，而我們知道宇宙馬最靠近的區域會是綠框，這樣一來我們就只要計算5, 6, 9, 10這四個子區域的點就好了，不需要搜尋所有16個區域的點。

以下是uniform和quad tree的比較，可以發現他們的差別在於對於空間的劃分，quad tree或kd tree根據每個點切出4或2個子空間；而uniform把整個空間切成一定的數量。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License