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转向了那一摞本子，开始念咒语。他对着那堆纸夸张地挥舞着手臂。突然一下，一个巨大的二叉搜索树出现在了空中。每个节点都写着一次调职申请的日期距离目前的天数。那些节点都浮在空中，之间被蓝色的线连着。