Frank又盯著那個調職列表看了幾分鐘，但沒能找到任何可疑的地方。最近調職的目的地都離首都——那些偷竊案的案發地——十分遙遠。最近的一個調職目的地為Easterville市——離首都有50英里遠，而這次調職的原因寫的是那位警官「長期的腳臭」。
「就這些了嗎？」Frank轉向Notation問道。
「對，」Notation有些不悅地說道，「這是所有曾在各個警察局之間調過職的警官名單了。」
Frank皺了皺眉頭。這種說法聽起來不太對，不太完整。「那初始分派呢？」Frank問道。
「從警察學院畢業時的調職記錄嗎？」Notation問道。
「對，」Frank說道，「從警察學院的調職記錄呢？」
「嗯，」Notation說道，「那些是見習期初始調職。那是記錄在另外的地方的。」
Frank慢慢地點了點頭。他開始快速地思考。
「我可以去……」Notation開始說道。
「不必了，」Frank打斷道，「我之前和警長說過我今天下午會去給他通報案情發展的。我可以順便把那些本子拿著。」
「你要去見警長？」Notation驚訝地問道。
「及時向客戶通報案情是私人偵探工作的一部分。」Frank說道。
「你也可以和警長說說Gretchen的猜想。」Socks補充道。
「什麼猜想？」Notation問道，她的眼睛在Socks和Frank之間遊走。
「Frank沒告訴你嗎？」Socks問道。
「沒有，」Notation咬著牙說道，「他並沒有告訴我。」她的手握起了拳頭，她的表情彷彿在說她非常想用那拳頭向Frank鼻子上打一拳。
「我的導師Gretchen認為明天晚上會有人攻擊城堡。」Socks說道。
「是嗎？」Notation問道，接著她轉向Frank說道，「聽起來這個信息很有用啊。你為什麼沒有告訴我？」
「這只是一個猜想，」Frank躲避著Notation的眼睛，邊聳了聳肩膀回復道。
「我應該和你一起去見警長。」Notation說道。
Frank退縮了，他沒有預料到這一層。除非有特別好的消息，否則沒有人會樂意去向Donovan警長報告案情。如果你走進他的辦公室，告訴他你遇到了好多條死路，發現一堆還沒來得及探索的線索，還有一些有生命危險的情況，你應該會被他狠狠地教訓一頓。如果不是Frank自己需要信息的話，他根本就不會想著去向警長報告案情。
「我需要你去追查另外一件事，」Frank在短暫地停頓後說道，「並行搜索，還記得嗎？」他將手伸進了口袋，但只找到了他的筆記本、一些食品包裝袋和一隻老舊的蝸牛殼，這只蝸牛殼是他上一個案子的紀念品。那是一個關於打擊樂隊和無數噪聲擾民投訴的案子。他將它從口袋中拿了出來。
「看看你能不能找出任何關於這個的消息。」他說道。
「一隻殼？」Notation問道，「這跟我們的案子有什麼關係？」
「我不知道，」Frank閃爍其詞地答道，「但『玻璃箱』Billy也許知道。」
Notation很不情願地接過了蝸牛殼，並開始研究它。她一邊將蝸牛殼在手中來回翻滾，一邊低聲說道：「為什麼偏偏要去找Billy。他這人幾乎從來都找不到。」
Frank轉向正十分困惑地盯著蝸牛殼的Socks，說道：「你能把這個搜索樹也帶到警察局嗎？」
「額，可以，」Socks說道，「但到那再重新建一個容易多了。」
Frank搖了搖頭：「要是重新建一個的話我們需要所有的本子。我可不想抱著它們走過大半個城市，看著就很重。」
聽到這，Notation暫時停下了對手中蝸牛殼的研究，又狠狠地瞪了Frank一眼。
57分鐘後，Frank和Socks站在了警局記錄處的門口。走這段路一般只需要20分鐘，但Socks面前那巨大的發著光的二叉搜索樹讓他們的速度放慢了許多。這棵樹不僅阻擋了他的視線，導致他一路上被好幾個車轍絆倒，還吸引了一大堆路人的目光和問題。Frank到最後只得大叫一聲「別擋道！這是危險的不穩定魔法物品」，這一招效果好極了。
「你不是要去找警長嗎？」Socks問道。
「我們先找到調職記錄再說。」Frank說道。他從來都不喜歡一無所獲地去見客戶。
每一屆警察學院都會帶來大約20個新警官，每一個都會被分派到王國中某個地方的警察局。因此，寫著近十屆畢業生去向的初始分派本至少有十磅重。和其他本子一樣，它們也是按名字而不是按日期排序的。
「看起來我們有幾百個調職記錄需要加到樹裡面。」當他們在休息室內找到一個空桌坐下時，Frank這樣說道。由於安保要求，加上公文數量巨大，沒有人可以在存放記錄的房間裡工作。因此，所有的警察局都會有至少一個與記錄室相鄰的房間，裡面放著桌子供大家使用。
「我們不能加節點！」Socks大聲說道。
「當然可以，」Frank說道，「往二叉搜索樹中加節點很簡單。從頂端開始，像尋找符合條件的值那樣向下搜索。當你走到一個盡頭時，把新的值加在它的下面就好了。
「我們以這個57天前的調職記錄為例。我們從頂端開始，因為57大於根節點裡面的55，所以我們向右走。接下來，因為57小於67，所以我們向左走。再接著，因為57小於61，所以我們再次向左走。現在比較57和59，我們應該再次向左走。但這個點並沒有左子節點了。因此，我們將新的點加成59的左子節點就好了。」
Socks看起來被嚇傻了。
「看，」Frank說道，「我再來給你演示一遍。這個調職記錄是89天前的。89大於55，所以我們向右走；89大於67，所以又向右走；89大於85，因此再向右走。這裡，因為89小於91，因此我們將它加成91的左子節點。」
「我不是這個意思，」Socks堅持道，「要是樹變得不平衡了怎麼辦？」
「這的確有可能發生，」Frank承認道，「當你向二叉搜索樹中添加元素的時候，樹可能會變得不平衡。不過我們的搜索依然可以進行。」
「但是搜索在不平衡的樹上會變得低效！」Socks抗議道。
「的確。」Frank承認道。
向樹中添加節點的過程中，有時會抵消掉平衡二叉搜索樹最大的優點之一——算法的高效率。將平衡二叉搜索樹的節點數量翻倍時，它的層數只會增加1。這就意味著在搜索一個元素時，即使你將搜索數據的數量翻倍，你的搜索也只需要多進行一步。然而，Socks是對的：這種高效率只有在樹左右平衡時才存在。在最壞的情況下，當樹成為了一長條直線時，要找一個元素就必須沿著這條直線一直找下去了。而當我們向其中添加任意值的時候，不一定能保證樹依然平衡。
「但這個險值得冒。」Frank最終這樣說道。
「但是……」
「如果我們的搜索沒有那麼高效率，也沒有關係。相比抱著那麼多本子走過大半個城市來說，這只是一個很小的代價。那些本子看起來重極了。」
警用算法導論：二叉搜索樹Ⅳ
節選自Drecker教授講義
向二叉搜索樹中加入節點和尋找一個節點類似。我們從根節點開始逐步向下，操作就和我們尋找想加入的值一樣。我們通過比較想加入的值和當前節點的值的大小，來決定是該向左下還是向右下走。當我們遇到死路時，也就是需要走的方向的子節點並不存在時，我們便將要加入的值插入到這個不存在的子節點的位置。
插入一個元素的計算量和樹的深度成正比。但是，我們不能保證在插入新節點時依然可以保持樹的平衡。事實上，當你按特定的順序插入時，樹很容易就會因為有很深的分支而變得不平衡。比如，如果我們按排好序的順序來插入數字，所有這些加入的節點都會沿著一條分支排列。
