首页 » 算法神探:一部谷歌首席工程师写的CS小说 » 算法神探:一部谷歌首席工程师写的CS小说全文在线阅读

《算法神探:一部谷歌首席工程师写的CS小说》20 将疑犯加到搜索树中

关灯直达底部

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教授讲义

向二叉搜索树中加入节点和寻找一个节点类似。我们从根节点开始逐步向下,操作就和我们寻找想加入的值一样。我们通过比较想加入的值和当前节点的值的大小,来决定是该向左下还是向右下走。当我们遇到死路时,也就是需要走的方向的子节点并不存在时,我们便将要加入的值插入到这个不存在的子节点的位置。

插入一个元素的计算量和树的深度成正比。但是,我们不能保证在插入新节点时依然可以保持树的平衡。事实上,当你按特定的顺序插入时,树很容易就会因为有很深的分支而变得不平衡。比如,如果我们按排好序的顺序来插入数字,所有这些加入的节点都会沿着一条分支排列。