22 公文字典树

在对调职记录进行两次完整的搜索后，Frank仍然没有发现任何可疑的人。更确切地说，他没有找到任何有明显迹象参与了密谋的人。此时，每个人仍都是他的怀疑对象。

“嘿，Notation的名字在这里。”Socks在第二次搜索的时候注意到。

Frank叹了口气，说：“当然会在那里，她刚刚从警察学院毕业。这是一本警察学院的警官分派记录。”

“她在学校表现得很好，是不是？”Socks在扫描她的调职记录时问。

“请注意，Socks，”Frank说，“记住，我们是寻找任何可疑的东西，而不是那些无关紧要的。”

“三个毕业生转移到了城堡，”Socks说，“或许我们应该对其中的某人进行更加深入的调查。Gretchen认为……”

“不，”Frank摇了摇头打断了Socks的话。他已经看过了这些调职记录，这三个人没有任何可疑之处。

“这里什么都没有。”Frank说。Socks本想反驳，Frank再次打断他：“你应该回到我的办公室。我向警长汇报完毕后就去那里找你，我们再一起看看还有没有什么别的线索。”

此时，Frank看到Socks的脸上显露出如释重负的表情，但是他不确定这是否只是自己的臆想。他知道有些新人为了躲过周会不仅会装作身患阑尾炎，甚至还甘愿去做手术，而Socks现在可以躲过与警长的会面了。

在去办公室找警长之前，Frank先去了趟档案室。当时警长只给了他案件的官方报告，并没有让他去犯罪现场进行调查，说不定在这里能幸运地找到一些线索。

档案管理员是一个名叫John Cache的人，在勉强同意Frank进入房间后便寸步不离地盯着他。这可能是因为盗窃之后警察局加强了防盗警戒，也可能仅仅是John Cache作为一个新手的急躁表现——每个新手都幻想着有一天能打击犯罪扭转局面呢。

Frank扫视整个书柜，假装在搜寻有关丢失宠物龙的信息。不出所料，这么大的警察局里，公文多如牛毛。现在每个政府组织的公文数量都在成倍地增长，更别说首都警察局了，其中的警官人数比任何其他两所警察局中的警官人数之和还要多。虽然这里有很多卷宗被偷走了，但房间里还是堆满了数不清的卷宗。

幸运的是，档案管理员已经将信息有效地组织起来。每个文档都必须遵守国王所颁布的《文书和十人以上机构工作文档的存储规则》，强制按照目录进行分类和存档。书柜中很大一部分都用于存储诸如逮捕报告、费用报告、调职记录、警卫轮岗和噪声投诉等文件了。

档案室看起来像是一个巨大的trie树。trie树，也称为前缀树，是一种可对字符串集合进行高效搜索的数据结构。它在概念上类似于二叉搜索树，也是首先从根节点开始，并一路向下扩展。但是，trie树是用来搜索字符串而不是数值的。在每一个节点，trie树都会根据字符串中的下一个字母来对原始数据进行拆分。因此，trie树中的每个节点都有很多子节点，包含了字母表中A～Z的每个字母。在这种结构中，只需沿trie树中的一条路径就可以高效地搜索出任意字符串，因为只需要根据目标字符串中的下一个字母就可以方便地选择出下一个节点。

Frank曾经在一个巫师大会上看到过这个神奇的trie树。一棵像霓虹灯样子的树倒挂在空中，显示着它所携带的一千多种不同药水的名字。为简单起见，这里的trie树只显示非空的子树。

客户可以使用trie树快速了解哪些商品有现货哪些商品缺货。例如，他们可以通过B、A、T、N、I和P这条分支来知道小贩今天携带了batnip；也可以迅速地知道今天baby powder缺货，因为此时BA的子树中没有B这个分支。

档案室采用了trie树的概念，并将其应用于书柜的管理上。26个巨大的书柜靠墙排列着，每个书柜上都记录了一个字母，它们是trie树的第一层节点。首先是A书柜，然后是B书柜，以此类推。

接下来，每个书柜包含若干个搁架，每个搁架对应了目录的第二个字母，这些层构成了trie树的第二层。

由于大部分两个字母的组合与现有的目录并不对应，因此每个书柜并不需要26个独立的搁架。每个搁架水平放置一些贴了标签的书挡，这些书挡就构成了trie树的第三层。

Frank一边走，一边看着V号搁架。他在警队的时候，就曾经成功游说为Vinettee集团专门开辟一个叫作Vinettees的目录。他花了很多晚上去研究书柜V搁架I书挡N上的文件。

此时，Frank停在书柜D搁架R书挡A处。他取出了一本有关宠物龙的档案假装在看它，同时搜寻着房间的其他地方。