17 二叉搜索树陷阱（第2/3页）

不幸的是，这种二叉搜索梯在艺术领域一直都未曾流行起来。这也许是因为它们体积太大了，而且还需要人不停地爬上爬下。不过很快它们就被犯罪分子们利用了起来。二叉搜索梯陷阱这种危险的东西是初级巫师Katia Ladderfell在为Vinettee集团卖命的时候发明的。Katia在每一层上放了一个数字标签，需要知道密码才能安全地通过这棵树。在设计这棵树和放置标签时，他延续了二叉搜索树的特性——一个节点的左子树中的数字一定会比当前数字小，而它的右子树中的数字一定会比当前数字大。在这棵被变成武器的二叉搜索树中，只有一条路是安全的，这条路便是通向最底层写着密码的那个节点的路径。如果你知道密码的话，你可以一层一层地从上到下去找这个数字。到达每一层时，你可以比较密码和当前数字的大小，从而决定是往左下方还是往右下方走。因此，Vinettee集团的恶棍们只需要记住一个密码就行了，而不需要记住一大串左右的选择。由于这群恶棍们大多不太聪明，所以这一点对于Vinettee集团格外重要。

如果你不知道密码而选择了错误的梯子的话，你就会触发一个机关。有时候这些机关是致命的，而有时候却只是吓你一下而已。一些常用的机关有：诅咒之梯、毒蜘蛛、从上面掉下的石头、飞镖和在空中摇晃的刀刃，还有时候选错梯子的人会受到一个魔法咒语的辱骂，辱骂他的外表、气味或智商等方面。

上一次Frank面对Vinettee集团的二叉搜索梯时，一个恶棍告密者告诉他密码是10。那一次Frank得以悄悄地来到他们的藏身点，并抓住了三个Vinettee集团的人，只有Rebecca Vinettee逃掉了。

要是他知道这个陷阱现在的密码的话，也许他还有机会抓住那个密探。

Frank头脑中闪过了一串思绪。首先，Vinettee集团会不会重复利用密码？他们的恶棍一般都很蠢，Frank不觉得他们可以记住很多数字。其次，由于现在已经没有多少邪恶巫师，这个二叉搜索梯一定有些年头了。在Exponentious巫师造反失败后，那些邪恶巫师们要么被改造了，要么躲起来了，就连Katia Ladderfell都逃到了一个小镇上，开了一个叶子农场。由于站在如此高的地方，Frank的腿已经开始有点发抖了。

Frank看了看脚下的根节点的平台上的标签，上面写着50。如果他想的没错，Vinettee集团用的还是同一个密码的话，因为10小于50，所以他应该往左下方走。

Frank担心地咒骂了几声，由左边的梯子向下爬去。这一路十分顺利：没有蜘蛛，没有刀刃，甚至连侮辱人的脏话都没有。

在下一个平台上，Frank找到了一个写着5的标签。由于10大于5，他需要向右边走下去。他越来越自信，一下跳到了右边的梯子。看来有的时候把敌人想得蠢一些是没错的。

下一个平台离地面只有一层，也就是20英尺了。Frank看到标签上写着25，便立刻往左边走去。

当他意识到有些不对时，他已经爬了一半了。他听见了一声吱吱的声音，同时他左脚下的那根横杆开始晃动了。他向下看时，正好看到横杆撞上了附近的一截铁棍，而他的左脚则被夹在了两者之间。他惊讶地叫了出来，眼睁睁地看着那节铁棍不断地上下移动。而铁棍每动一次，他的脚就又感到一阵疼痛，简直就像是梯子在咬他的脚一样，他甚至可以感受到脚下的金属梯子在慢慢长出牙齿。

趁梯子还没有开始咬他的手，Frank毫不犹豫地跳了下去。由于脚还在因为之前被咬而疼痛，他非常笨拙地落到了地上，前后趔趄了几步后才稳住。

他不由自主地转了一圈，随即看向梯子下面的标签，上面清楚地写着10——他走的路是正确的。但随即他注意到了附近的地板上用粉笔写的一小行字：“不要使用。密码改了。”Frank顿时继续开始骂了起来。

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

节选自Drecker教授讲义

二叉搜索树是一个数据结构，它储存信息的方式和二分搜索中使用信息的方式类似。树中的每一个节点存放一个值，并且每个节点最多有两个子节点：一个左子节点和一个右子节点。节点的位置根据其中存放的值的大小来定。所有左子节点和它的左子节点中存放的值都比当前节点中的值小；类似的，所有右子节点和它的右子节点中存放的值都比当前节点的值大。