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

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

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

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

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

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

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

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

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

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

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

节选自Drecker教授讲义

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

要高效地在二叉搜索树中查找一个值，可以从最上面的节点（根节点）开始往下查找，每查找一步就比较要找的值和当前节点的值的大小，以决定是该向左查找还是向右查找。如果要找的值比当前值小，我们就向左查找：

而如果要找的值比当前值大，我们就向右查找：

当我们找到要找的值，或者遇到一条死路的时候，搜索就结束了。如果我们遇到了一条死路，就可以确定我们要找的值在树中并不存在。

如果对于每个节点，其左子树中的节点数量都和其右子树中的节点数量一致，我们就可以说这个二叉搜索树是完全平衡的。在这种情况下，如果我们将树中的节点数量翻倍，整棵树的高度只会增加1。

这种搜索的计算量与目标值在树中的深度是成正比的。位置越深，我们需要进行比较的次数就越多。