18 建造二叉搜索梯

“没想到我们会换密码吧，Runtime先生？”Frank听到身后的一个声音问道。

Frank转过头去。眼前的那位密探正从容不迫地向他走来。Frank试图站起来，但他的脚却疼得要命。最终，他还是坐在了地上，转过身去看着她。

“我没想到Vinettee集团居然有能力换密码。”Frank承认道，“这年头想要找邪恶巫师都很困难了。我听说撑到最后的邪恶巫师现在都开始卖椰子了。”

“的确很困难。很多邪恶巫师都逃跑了，或者改行从商了。但想找到一个也不是完全不可能。总之Vinettee集团找到了一个愿意帮助他们，但同时也有求于他们的巫师。”

她向梯子的方向挥了挥手，说道：“当然，在建造二叉搜索梯陷阱上他并没有Katia那么有天赋，Katia在这方面简直是一个艺术家。不过他的能力也足够了。

“其实你差一点就走对了。你只走错了一个梯子。现在的密码是26。因为我们不想让他改动太多的梯子，只改动一个，让我们可以抓到那些试图用旧密码的人就够了。真可惜。”

Frank在她说完之前一直保持着沉默。然后他问道：“你是谁？”

“我的名字并不重要。我是帮Vinettee集团做事的。”

“一个密探吗？”

她耸了耸肩：“我只是搜集信息的人。你叫我什么都行。”

“那你想从我这得到什么？”

“当然是想让你别多管闲事了。”

Frank仔细思考了一下。要让自己放弃追查，仅仅让梯子咬自己的脚很明显是不够的。眼前的密探显然也知道这一点，所以看来她要么会杀掉他，要么会将他关起来。虽然这两者都不怎么理想，但Frank终归还是希望自己不要被杀掉。

那个密探似乎看穿了他的想法，说道：“我本来以为二叉搜索梯陷阱已经足够让你放弃了，但现在看来这还不够。”她走向26对应的梯子旁边的那个梯子，并用手掌击打了梯子的一截，梯子发出一声闷响。紧接着她又击打了梯子两下，砰！砰！又是两声闷响。

“再见了，Runtime先生。”她说道，然后便目不回望地走了。

Frank疑惑地望着她走远。紧接着，他的余光注意到一丝动静，定睛一看，梯子上的三根铁横杆掉了下来。过了一会儿，那些杆开始嘶嘶地向他蠕动——它们原来是铁蛇。

Frank迅速地动了起来。那些铁蛇虽然很危险，但它们爬得很慢。如果他能成功到达26号梯子那儿的话，他就还有救。由于他的脚依然很疼，他只好用手和膝盖爬行着。接着，他用手拉着梯子让自己站起来，并用身子靠在那个金属梯子上。毫无疑问，爬上去的过程将会非常痛苦。

现在铁蛇距离他只有几英尺远了。

Frank恼怒地嚎叫了一声，起身爬上了梯子。其实那更像是在跳跃而不是在爬，因为他需要用那只未受伤的脚让自己跳起来，然后再用双手抓住上一级的梯子。每一步都伴随着他左脚的一阵疼痛。

Frank终于爬了上去，他瘫在了25号梯平台上。他一边躺着调整自己的呼吸，一边咒骂着二叉搜索梯，简直无法想象自己曾经还觉得这种数据结构很美丽很优雅。之前在警察学院的时候，Frank还专门去过Alena办的几个展览，而且他还去看过全世界仅有的一次二叉搜索树表演。

那场表演的名字叫“建造梨子”。Alena让三个巫师现场用魔法建了一个二叉搜索梯，将一堆藏画按照其中梨子的数量整理和展示了出来。当年以梨子为中心的静态画非常流行。有人觉得这可能是因为那年苹果的收成不太好。虽然对梨子的这种狂热不及下一年对吐司雕塑的崇拜那么令人尴尬，但是这段历史在现在的艺术史课上也只是会被带有一丝厌恶地匆匆带过。

接着，七个助手一人拿着一幅画着梨子的画走进了展览厅。他们按照画中梨子的数量由少到多站好。每个人都将手中的画举在自己的脸前方，以掩饰自己对梨的狂热。

第一个巫师上前了一步，他找出了最中间的那幅画。那幅画中画着一张木桌，上面放了一杯牛奶和8个梨子。

“树根上升！”那位巫师叫道。那一排画便立刻分成了三组。左边组里的画中的梨子数量都小于8，而右边组里的画中的梨子数量都大于8。浮在这两组上方的便是这个二叉搜索树的树根。这位巫师已经建好了这棵树的第一层分支。

接下来，另外两个巫师分别递归着分割了两边的画，过程与之前一样：每个巫师选出一堆画中最中间的那个，并将剩下的画分成了左右两份。随着他们的划分，树也就长出了新的分支。

在当时，整个表演看起来棒极了。但现在，坐在已经被变成武器的二叉搜索树上面，Frank觉得这整个想法实在太愚蠢了。他简直无法理解当时他为什么会觉得这种递归分割画的方式很有美感。

耳边的嘶嘶声将Frank的思绪带回了现实。一条铁蛇的头爬上了平台，正在寻找Frank。眼前的蛇其实只是一条会动的铁栏杆，它们没有眼睛，没有鼻子，也没有嘴巴。Frank很不能理解它们到底是用什么来寻找的。也许它们能感应到震动？

他想把蛇踢下去，但最终决定不这样做。因为铁蛇虽然并没有嘴巴，但毒性却难以置信得大。

Frank决定继续撤退。他走到了上一层梯子旁边，并将自己拉了上去。这时候他的脚踝已经没有那么疼了，所以他得以以一个正常的姿势来爬这截梯子。

Frank一直向上爬着。一会儿便回到了顶层写着50的那层平台。

他定了一会儿神儿，心中再一次开始咒骂二叉搜索梯。虽然没有任何具体的理由，他现在坚信二叉搜索梯是一个愚蠢的设计。Frank满意地点了点头，爬回了街道上，逃离了那些铁蛇。

警用算法导论：二叉搜索树Ⅱ

节选自Drecker教授讲义

你可以从一个排好序的数组中创建出一棵二叉搜索树。你只需要不断递归地将所有元素划分成更小的集合。在每一层中，选择最中间的那个元素作为那一层的节点。如果元素个数为偶数，那么随意选择中间两个元素中的一个就行。

创建好根节点之后，可以用同样的方式来分割左边的元素和右边的元素。从概念上来说，我们将排好序的数组分成了左右两个数组，并将同样的算法作用于它们上面。