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

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

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

不幸的是，这种二叉搜索梯在艺术领域一直都未曾流行起来。这也许是因为它们体积太大了，而且还需要人不停地爬上爬下。不过很快它们就被犯罪分子们利用了起来。二叉搜索梯陷阱这种危险的东西是初级巫师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担心地咒骂了几声，由左边的梯子向下爬去。这一路十分顺利：没有蜘蛛，没有刀刃，甚至连侮辱人的脏话都没有。