Frank又盯着那个调职列表看了几分钟，但没能找到任何可疑的地方。最近调职的目的地都离首都——那些偷窃案的案发地——十分遥远。最近的一个调职目的地为Easterville市——离首都有50英里远，而这次调职的原因写的是那位警官“长期的脚臭”。
“就这些了吗？”Frank转向Notation问道。
“对，”Notation有些不悦地说道，“这是所有曾在各个警察局之间调过职的警官名单了。”
Frank皱了皱眉头。这种说法听起来不太对，不太完整。“那初始分派呢？”Frank问道。
“从警察学院毕业时的调职记录吗？”Notation问道。
“对，”Frank说道，“从警察学院的调职记录呢？”
“嗯，”Notation说道，“那些是见习期初始调职。那是记录在另外的地方的。”
Frank慢慢地点了点头。他开始快速地思考。
“我可以去……”Notation开始说道。
“不必了，”Frank打断道，“我之前和警长说过我今天下午会去给他通报案情发展的。我可以顺便把那些本子拿着。”
“你要去见警长？”Notation惊讶地问道。
“及时向客户通报案情是私人侦探工作的一部分。”Frank说道。
“你也可以和警长说说Gretchen的猜想。”Socks补充道。
“什么猜想？”Notation问道，她的眼睛在Socks和Frank之间游走。
“Frank没告诉你吗？”Socks问道。
“没有，”Notation咬着牙说道，“他并没有告诉我。”她的手握起了拳头，她的表情仿佛在说她非常想用那拳头向Frank鼻子上打一拳。
“我的导师Gretchen认为明天晚上会有人攻击城堡。”Socks说道。
“是吗？”Notation问道，接着她转向Frank说道，“听起来这个信息很有用啊。你为什么没有告诉我？”
“这只是一个猜想，”Frank躲避着Notation的眼睛，边耸了耸肩膀回复道。
“我应该和你一起去见警长。”Notation说道。
Frank退缩了，他没有预料到这一层。除非有特别好的消息，否则没有人会乐意去向Donovan警长报告案情。如果你走进他的办公室，告诉他你遇到了好多条死路，发现一堆还没来得及探索的线索，还有一些有生命危险的情况，你应该会被他狠狠地教训一顿。如果不是Frank自己需要信息的话，他根本就不会想着去向警长报告案情。
“我需要你去追查另外一件事，”Frank在短暂地停顿后说道，“并行搜索，还记得吗？”他将手伸进了口袋，但只找到了他的笔记本、一些食品包装袋和一只老旧的蜗牛壳，这只蜗牛壳是他上一个案子的纪念品。那是一个关于打击乐队和无数噪声扰民投诉的案子。他将它从口袋中拿了出来。
“看看你能不能找出任何关于这个的消息。”他说道。
“一只壳？”Notation问道，“这跟我们的案子有什么关系？”
“我不知道，”Frank闪烁其词地答道，“但‘玻璃箱’Billy也许知道。”
Notation很不情愿地接过了蜗牛壳，并开始研究它。她一边将蜗牛壳在手中来回翻滚，一边低声说道：“为什么偏偏要去找Billy。他这人几乎从来都找不到。”
Frank转向正十分困惑地盯着蜗牛壳的Socks，说道：“你能把这个搜索树也带到警察局吗？”
“额，可以，”Socks说道，“但到那再重新建一个容易多了。”
Frank摇了摇头：“要是重新建一个的话我们需要所有的本子。我可不想抱着它们走过大半个城市，看着就很重。”
听到这，Notation暂时停下了对手中蜗牛壳的研究，又狠狠地瞪了Frank一眼。
57分钟后，Frank和Socks站在了警局记录处的门口。走这段路一般只需要20分钟，但Socks面前那巨大的发着光的二叉搜索树让他们的速度放慢了许多。这棵树不仅阻挡了他的视线，导致他一路上被好几个车辙绊倒，还吸引了一大堆路人的目光和问题。Frank到最后只得大叫一声“别挡道！这是危险的不稳定魔法物品”，这一招效果好极了。
“你不是要去找警长吗？”Socks问道。
“我们先找到调职记录再说。”Frank说道。他从来都不喜欢一无所获地去见客户。
每一届警察学院都会带来大约20个新警官，每一个都会被分派到王国中某个地方的警察局。因此，写着近十届毕业生去向的初始分派本至少有十磅重。和其他本子一样，它们也是按名字而不是按日期排序的。
“看起来我们有几百个调职记录需要加到树里面。”当他们在休息室内找到一个空桌坐下时，Frank这样说道。由于安保要求，加上公文数量巨大，没有人可以在存放记录的房间里工作。因此，所有的警察局都会有至少一个与记录室相邻的房间，里面放着桌子供大家使用。
“我们不能加节点！”Socks大声说道。
“当然可以，”Frank说道，“往二叉搜索树中加节点很简单。从顶端开始，像寻找符合条件的值那样向下搜索。当你走到一个尽头时，把新的值加在它的下面就好了。
“我们以这个57天前的调职记录为例。我们从顶端开始，因为57大于根节点里面的55，所以我们向右走。接下来，因为57小于67，所以我们向左走。再接着，因为57小于61，所以我们再次向左走。现在比较57和59，我们应该再次向左走。但这个点并没有左子节点了。因此，我们将新的点加成59的左子节点就好了。”
Socks看起来被吓傻了。
“看，”Frank说道，“我再来给你演示一遍。这个调职记录是89天前的。89大于55，所以我们向右走；89大于67，所以又向右走；89大于85，因此再向右走。这里，因为89小于91，因此我们将它加成91的左子节点。”
“我不是这个意思，”Socks坚持道，“要是树变得不平衡了怎么办？”
“这的确有可能发生，”Frank承认道，“当你向二叉搜索树中添加元素的时候，树可能会变得不平衡。不过我们的搜索依然可以进行。”
“但是搜索在不平衡的树上会变得低效！”Socks抗议道。
“的确。”Frank承认道。
向树中添加节点的过程中，有时会抵消掉平衡二叉搜索树最大的优点之一——算法的高效率。将平衡二叉搜索树的节点数量翻倍时，它的层数只会增加1。这就意味着在搜索一个元素时，即使你将搜索数据的数量翻倍，你的搜索也只需要多进行一步。然而，Socks是对的：这种高效率只有在树左右平衡时才存在。在最坏的情况下，当树成为了一长条直线时，要找一个元素就必须沿着这条直线一直找下去了。而当我们向其中添加任意值的时候，不一定能保证树依然平衡。
“但这个险值得冒。”Frank最终这样说道。
“但是……”
“如果我们的搜索没有那么高效率，也没有关系。相比抱着那么多本子走过大半个城市来说，这只是一个很小的代价。那些本子看起来重极了。”
警用算法导论：二叉搜索树Ⅳ
节选自Drecker教授讲义
向二叉搜索树中加入节点和寻找一个节点类似。我们从根节点开始逐步向下，操作就和我们寻找想加入的值一样。我们通过比较想加入的值和当前节点的值的大小，来决定是该向左下还是向右下走。当我们遇到死路时，也就是需要走的方向的子节点并不存在时，我们便将要加入的值插入到这个不存在的子节点的位置。
插入一个元素的计算量和树的深度成正比。但是，我们不能保证在插入新节点时依然可以保持树的平衡。事实上，当你按特定的顺序插入时，树很容易就会因为有很深的分支而变得不平衡。比如，如果我们按排好序的顺序来插入数字，所有这些加入的节点都会沿着一条分支排列。