19 疑犯的二叉搜索树

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叹了口气，解释道：“递归的意思是将同样的算法作用于一个子问题上。在我们的问题中，我们将同样的搜索算法作用于子节点上，就是以同样的方法去检查它们。

“我们只需要检查一下我们需不需要探索子节点。如果需要的话，就用同样的算法去检查它们。我们可以很容易地比较当前点的值是否在我们要找的区间里。如果当前点的值比我们要找的区间中的最小值还要小的话，就可以知道所有在其左子树中的值都不在我们要找的区间里。因此可以跳过那一个子树。反过来，如果当前节点的值比我们要找的区间中的最小值要大的话，我们就需要继续在其左子树里面搜索。