在对调职记录进行两次完整的搜索后，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处。他取出了一本有关宠物龙的档案假装在看它，同时搜寻着房间的其他地方。
警长说的没错。书柜中前缀为AS、CE、EX、NO、PR和RO的搁架里的文件全部被搬空了，而其他的却完好无损。他暗暗地记住了这些前缀，被偷走的这些前缀的文件中一定暗藏着什么信息。Frank有了另外一条线索。
他把手中的书放回到Dragon书柜的Registrations号搁架处，大声宣布：“好消息！档案记载首都只有几只食鸽龙，不过却有很多的鸽子。等我找到它时，至少那只可怜的龙不会被饿死。”
当Frank从档案室大步走出来的时候，John Cache怜悯地看了他一眼，什么也没有说。
警用算法导论：trie树
节选自Drecker教授讲义
trie树是基于树的数据结构，用户可以很方便地通过某个字符串的前缀来搜索到目标字符串。与二叉搜索树一样，trie树也是首先从根节点开始，然后一步步向下选取分支节点。在trie树中，每一个节点下的分支数（即有多少个子节点），取决于所有字符串中当前节点字母的下一个元素有多少种不同的可能。所以，trie树的每个节点可能不止两个子节点。
和二叉搜索树一样，我们只需将数据中出现过的节点依次插入到trie树中。例如，现在有单词ZAP、ZEN、ZONE和ZOOM。因为此时并没有ZONK这个单词，所以我们并不需要在ZON下面再设一个节点为K的子树。
注意，我们不需要在每个节点中存储一个字符串的所有可能的前缀，而是可以根据需要通过从树根到该节点的路径来重建出这个前缀。但是，有时也需要在每个节点中存储一些额外的信息，比如标记该节点是否为一个字符串或者单词的最后一个字母，以便我们区分当前插入的是一个单词还是一个单词的前缀。例如，我们无法确定树中的ZOO是否为一个独立的单词，因为还有一个单词是ZOOM。
trie树的搜索过程类似于二叉搜索树的搜索过程。算法从trie树的顶部开始向下进行。在每个节点，决定接下来应该选取哪个分支就需要看目标字符串的下一个字母是什么。例如，需要搜索ZEN这个字符串，搜索路径为：从Z开始，接着选择E这个分支，最后选择N这个分支。
如果找不到这样的节点，就可以确定我们所需要的单词（字符串）不在树中。所以，如果我们在这棵树上搜索ZANY，我们会发现ZA之后便无路可走。
令人惊讶的是，警务中常常用trie树来编制犯罪嫌疑犯名单。举报者常常拒绝提供一个完整的名字，只会提供名字的前几个字母。此时，我们就可以使用trie树来对名字的前缀进行搜索，便可以得到与该前缀相匹配的所有人的名字。依据字母的数量和特殊性，这些信息足以大幅减少搜索范围。