Frank踉踉蹌蹌地走回了自己的辦公室，Socks正在那等著他。這位年輕的巫師坐在Frank的椅子上漫無目的地轉著。Frank盯著Socks，直到他意識到了自己的錯誤才罷休。Socks低聲地道了歉後，從椅子上跳了起來。
「你找到什麼了？」Frank問道。
Socks聳了聳肩說道：「沒有什麼有用的。」
「什麼都沒有？」Frank問道。
「那些巫師都沒有聽說過有什麼新的聯盟，」Socks迅速地補充道，「最後一個成立的巫師聯盟是魔法甜品商聯盟，是去年為了應對那些次品薄荷而成立的。還記得那些餐館中的小軟粒嗎？一開始吃起來還覺得它們像薄荷，但在接下來的六個小時裡都會覺得自己吞下了松針。簡直就像有人在做惡作劇一樣。魔法甜品商聯盟解決了這些薄荷的問題，然後便開始做關於巧克力和咖啡的勾當。這個聯盟擁有六個甜品店和四車的……」
「沒什麼別的了嗎？」Frank打斷道。
Socks搖了搖頭說道：「我還詢問了關於俱樂部和聯合會的事情，」他說道，「唯一新成立的便是Babbageville巫師保齡球聯合會，但它只存在了不到一個月。顯然Babbageville沒有多少喜歡打保齡球的巫師。」
Frank歎了口氣。他本來也沒有指望能從Socks的調查中得到什麼有用的消息，但這麼徹徹底底的一無所獲還是讓他有些失望。
「你呢？」Socks問道。
「嗯，」Frank回答道，「我找到了一個新的線索。」
「真的？是什麼？」
Frank還沒來得及回答，Notation警官就抱著一大摞本子走進了辦公室。她走到了Frank的桌子前，並將那一摞本子砸在了桌上。桌子在重壓下都有些下沉了。
「過去一年的所有調職和分派記錄，」她氣喘吁吁地說道，「現在你能告訴我為什麼要我去找這些了嗎？」
「我們需要找到一次調職的記錄。」Frank說道。
「我猜到了，」Notation說道，「但如果你告訴我要找的是什麼，我可以就在那裡找而不必都搬來。」
「我並不知道是哪一次。」Frank解釋道，這句話半真半假，因為即使他知道，他還是會讓Notation把所有的記錄都拿回來。他需要在搜索的時候在場，他需要確保沒有東西被遺漏了。
「好吧，」Notation說道，「我們在找什麼？」
「我們要找所有50天到70天前的可疑的調職記錄，」Frank說道，那些日子大致是監獄裡找到的賬本裡面被撕掉的那些日期，「這是一個區間查找。我們需要找到一個日期區間內的所有調職記錄。」
Notation呻吟了一聲說道：「這些記錄是按人員原來的分配地址排序的，如果地址相同，就會按警官姓名排序。它們並沒有按照日期來索引。我們需要一個個地去看每一條記錄，這需要花上好幾個小時。」
「不，並不需要，」Frank說道，「因為我們可以用魔法去找。」
Socks驚訝地抬起頭。「魔法？」他問道，「我不知道任何區間查找的魔法。」
「你知道二叉搜索樹。」Frank回答道。
「我是一個二叉搜索樹的專家，」Socks同意道，「但我不知道這有什麼用？」
「我們可以建一棵調職申請的二叉搜索樹。每個點的值便是調職申請日期到今天之間的間隔天數。接下來我們就可以在樹上做區間搜索了。」
「在樹上做區間搜索？」Socks問道。
「為什麼還要用一棵樹？」Notation問道，「如果我們只需要做一次搜索，建樹所花的時間比瀏覽一遍花的時間還要長。」
Frank聳了聳肩說：「我覺得我們還會需要做其他搜索的。如果Socks用魔法把這棵樹建出來，我們就可以搜索多次了。」
「但我不知道如何做區間搜索啊！」Socks抗議道。
「你先把樹建出來。我會告訴你怎麼搜索。」
「好，」Socks說道，「這需要一些時間，我只習慣用buttons來建樹，現實中真正存在的buttons。我還從來沒有用它來整理過信息。我需要更改一下我的咒語。」
Socks趴在Frank的桌上，在一張羊皮紙上寫著更改後的咒語，這時Notation直截了當地問Frank道：「到底發生什麼了？」
「沒什麼。」Frank說道。
「你就算了吧，」Notation生氣地說道，「自從去了監獄之後，你就在隱瞞著什麼。為什麼我們需要查調職記錄？你為什麼之前從來沒有提到過這個？你們到底發現什麼了？」
「我都說了，只是我的直覺。」
「我不信。你在對我隱瞞什麼？」
Frank沒有回答。
「改好了，」Socks說道，「至少我覺得改好了。我們過一會兒就知道了。」
Socks轉向了那一摞本子，開始唸咒語。他對著那堆紙誇張地揮舞著手臂。突然一下，一個巨大的二叉搜索樹出現在了空中。每個節點都寫著一次調職申請的日期距離目前的天數。那些節點都浮在空中，之間被藍色的線連著。
「現在我們來進行區間搜索。」Frank說道。
「我之前說過，我不會……」Socks說道。但Frank揮手制止了他。
「我們用一個改編版本的深度優先搜索，」Frank解釋道，「從最上面的節點開始，由上到下地查找。」
「怎麼查找？」Socks問道。
「對每一個節點都進行三個步驟的操作。首先，你看這個節點本身是不是在區間裡面。如果是，比如這裡的55天在區間裡，我們就將它加入到我們的結果中。否則我們就忽略它。」
「等等，」Socks說道，「我給我們找到的結果標上另一種顏色好了。深綠色怎麼樣？」
「好。隨便你，」Frank回復道，「在檢查完當前節點後，再看看我們是否需要往兩個子節點裡面探索。如果需要就遞歸探索左右兩個子節點。當然，只有在一個子節點裡面的範圍可能和我們要找的範圍重合時才需要遞歸探索那個子節點。」
「遞歸探索？」Socks問道。
Frank等著，想看看Notation會說出什麼樣的學術定義。但她卻異常地沉默。Frank歎了口氣，解釋道：「遞歸的意思是將同樣的算法作用於一個子問題上。在我們的問題中，我們將同樣的搜索算法作用於子節點上，就是以同樣的方法去檢查它們。
「我們只需要檢查一下我們需不需要探索子節點。如果需要的話，就用同樣的算法去檢查它們。我們可以很容易地比較當前點的值是否在我們要找的區間裡。如果當前點的值比我們要找的區間中的最小值還要小的話，就可以知道所有在其左子樹中的值都不在我們要找的區間裡。因此可以跳過那一個子樹。反過來，如果當前節點的值比我們要找的區間中的最小值要大的話，我們就需要繼續在其左子樹裡面搜索。
「對於右子樹也是同樣的道理。如果當前點的值比我們要找的區間中的最大值還大的話，我們就可以跳過右子樹。否則，就需要繼續向右子樹裡面搜索。
「現在我們要找的區間是50到70。對於這個節點55，由於其左子樹中的值最大可能是55，所以其中的點可能會落在我們要找的區間中，所以我們需要去探索左子樹。右子樹裡面的值可能會大於55，這也和我們要找的區間有重疊，所以我們也需要探索右子樹。我們先從左子樹開始。
「現在的節點上顯示的是22天，」Frank繼續說道，「我們不需要將它放進結果列表。並且，因為所有在它左子樹裡面的值都會比22小，因此我們也不需要去檢查它的左子樹了。」
「我們把這種情況叫作搜索中的剪枝
，」Notation補充道，「因為這就像從一棵樹上面砍下了一個分支一樣。」
當Frank看向她的時候，她想起來她不應該和Frank說話，便又沉默了。
「所以我們只要探索右邊的分支就好。」Frank說道。
「遞歸著探索！」Socks補充道，聽起來他簡直太歡樂了。
「對，遞歸著探索，」Frank冷淡地同意道，「現在的節點上是38天。同樣的，我們不需要將它加到結果列表中，並且我們也可以跳過它的左子樹。」
「但我們需要遞歸探索它的右子樹。」Socks說道。看起來他挺享受這個新的算法。
Frank點了點頭。
下一個點沒有子節點了。它已經是一條死路了。
「現在呢？」Socks問道。
「和深度優先搜索一樣，」Frank說道，「我們倒退，並且選擇之前還沒有探索過的路線，直到我們將整棵樹都搜索過了為止。因為我們一路上剪掉了很多分支，所以我們需要一直倒退到根節點。」
搜索接著在根節點的右子樹裡開始了。被找到的新記錄被加入了結果列表，不合適的分支被一個個剪掉，而合適的分支則被遞歸地探索著。
最後他們找到了幾條符合條件的調職記錄。Frank仔細地研究了找到的結果，試圖找出任何可疑的地方。
「什麼都沒有，」他難以置信地低吼了一聲，「這裡面什麼都沒有！」
警用算法導論：二叉搜索樹Ⅲ
節選自Drecker教授講義
在二叉搜索樹上進行區間查找和查找一個元素類似。算法從最頂端的根節點開始，一路遞歸著搜索整棵樹。它根據以下三個條件來對在每一個節點做決定：
1.當前節點應該被算在結果中嗎？如果當前節點在要找的區間內，我們就應該將它加到結果列表中。
2.應該探索左子樹嗎？如果當前節點有左子樹，並且當前節點的值大於區間裡最小值，我們就應該遞歸探索它的左子樹。因為這種情況下，它的左子樹可能包括區間內的值。
3.應該探索右子樹嗎？如果當前節點有右子樹，並且當前節點的值小於區間裡最大值，我們就應該遞歸探索它的右子樹。因為這種情況下，它的右子樹可能包括區間內的值。
使用二叉搜索樹來做區間搜索的優勢在於，可以通過剪去大量不可能包含要找的值的分支來減少計算量。
考慮如下的二叉搜索樹：
如果想找在區間[8，20]內的所有值，你只需要訪問全部25個節點中的7個（被訪問的節點被標上了陰影）：
類似的，如果想找在區間[70，80]內的所有值，你只需要訪問全部25個節點中的6個：
需要注意的是，訪問一個節點不一定代表這個節點會被包括在最終結果列表裡。在我們給出的兩個例子中，可以看到算法也需要訪問一些不在目標範圍內的節點。之所以訪問它們，是因為那些節點的子樹可能包括我們想找的值。
和尋找一個值一樣，用二叉搜索樹做區間搜索只有在需要進行多次搜索時才高效。建立一棵二叉搜索樹比搜索一遍數據需要更大的計算量。但是如果要搜索多次，這個計算量可以被均攤到多次搜索裡，從而讓每次搜索的平均計算量變小。
1 剪枝，這是一個很形象的說法。在搜索算法優化中，就是通過某種判斷，避免一些不必要的遍歷過程。簡單是說就是不用去遍歷每個節點，形象點說就是剪去了搜索樹中的某些肯定不需要考慮的「枝條」，故稱剪枝。——譯者注返回