17 二叉搜索树陷阱

在距离Cloaks andMore店不到一个街区的地方，Frank注意到有一个女人在跟踪他。即使十分恼怒，Frank也不得不承认她的跟踪技术很好。她一直走在街对面，在Frank后面至少30英尺的地方，她还时不时地通过商店窗户上的反光来观察Frank。并且她穿了一件没有任何特点的深绿色披风，这种颜色的披风在街上随处可见。

Frank突然停下来，弯下腰，假装自己在系鞋带。这是两种最常见的识别跟踪者的方法之一。另外一种则是突然向一个随意的方向快步走去，看看有谁会跟上来。虽然可能后者更加有效，但系鞋带这个动作动静更小，而且更重要的是，不需要人跑动。

跟踪者向前走过了Frank，却在前方十英尺的地方停了下来。她看起来仿佛在看一家玻璃透亮的商店里卖的卷心菜。

Frank站了起来，转身向反方向走去。过了半个街区，他横穿马路，愤怒的驴车驾驶员对他大喊大叫，Frank完全无视了他。Frank走到了马路的另一边，也就是跟踪者行走的一边。他随即向一个小巷中走去。一走进小巷，Frank便停了下来，开始等待。

当跟踪者匆忙跑过转角的时候，她几乎撞到了Frank身上。

“嗨，”Frank说道，“你为什么要跟着我？”他尽量让自己的语气平淡一些，但这在平时都是不可能的，这次虽然他没有尖叫，但语气还是像低吼一般。

职业密探一般都会花很长时间来计划如果被发现了该如何应对。他们有一大堆故事，用来在各种场合下圆场。他们甚至可以解释自己为什么会带着窃听装置和假乌龟出现在皇家宫殿中。他们的梦想就是能在这种情况下通过谎言来顺利过关。但现实一般不会如此顺利——他们经常会在意想不到的时候被发现。就像现在，Frank就希望能出其不意地抓住她。

但跟踪者异常专业，一点都没有紧张或者惊讶的迹象。她脸上露出了一丝愤怒，随后她丢下一颗烟雾弹，消失了。

就算她不丢烟雾弹，Frank也不可能追上她。在Frank反应过来准备去抓她的时候，她已经在街上跑远了。Frank咒骂了一声，穿过烟雾开始追她。

追了不到半个街区，Frank决定开始用深度优先搜索。这种情况下，密探一般都会尽快离开主路，试图逃离被追者的视线。大多数时候这都是一个很好的策略，但在这块几乎没有什么岔路的街区却明显行不通。

Frank边跑边将身边的街道想象成一个图。岔路口和死路的尽头是这个图上的点，而连接它们的路则是连接一个点与另一个点的边。

快速计算了一番后，Frank意识到在他落下太远之前，他只来得及搜索五六条岔路。这也是用深度优先搜索来追人所固有的缺陷。

Frank搜索完前两条街时一无所获。其中最像犯罪行为的便是一群孩子们在墙上涂鸦，他们用一根烧焦的木棍在墙上写了“递归之队”和“递归永恒”。Frank继续他的搜索。

又搜索过几条死路后，Frank正想着放弃，此时他在泥地中找到了一串通向一个打开的下水道口的脚印。他一边靠在墙上试图调整自己的呼吸，一边想着眼前的下水道肯定是她逃走的路。

Frank望向漆黑的下水道内，但什么都看不见。他爬进下水道，落在了一个木制平台上。他一边弯下腰，尽量让自己暴露的面积变小，一边巡视着这个房间。他所在的平台是固定在石墙上的，而它的下方是至少50英尺高的一间房子。唯一的一丝光是从头顶的下水道口照进来的，像一个位于远处的聚光灯一般。他看到那个密探从光照亮的椭圆形中跑过，跑向了对面的那堵墙。现在Frank已经被她甩掉很远了。

Frank思考着该如何选择。在他下面还有其他的平台，互相之间有20英尺的距离，并以铁梯子连接着。当他注意到地板上嵌着的黄铜标签时，他忍不住咒骂了一声：他现在正站在一个二叉搜索梯的顶端。

二叉搜索梯最先是由Alena Branche（一位奇异艺术馆馆长）为了整理自己的藏画而设计的。它们本质上就是一个巨大的二叉搜索树——一种为了高效查找而设计的数据结构。整个结构像一棵巨大的上下颠倒的树，而最上方的一个平台叫作根节点。从每一个平台向下都会分出最多两个梯子，而每一个梯子则通向另一个子节点，也就是下一层的另一个平台。整个结构在向下的过程中不断地分叉，使得整个结构中有着很多不同的路径。

作为一个追求细节的狂热分子，Alena原本是用这个结构中描绘的叶子数量来整理她的藏画。她的整理方法很简单：对于任何一个平台来说，其所存放的画中描绘的叶子数量，一定多于其左下方梯子通向的平台（左子树）中的画中描绘的叶子数量，且一定少于其右下方梯子抵达的平台（右子树）中的画描绘的叶子数量。这样你就可以从顶端开始选择路径找到含有特定叶子数量的画。