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 剪枝，这是一个很形象的说法。在搜索算法优化中，就是通过某种判断，避免一些不必要的遍历过程。简单是说就是不用去遍历每个节点，形象点说就是剪去了搜索树中的某些肯定不需要考虑的“枝条”，故称剪枝。——译者注返回