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

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

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

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

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

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

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

节选自Drecker教授讲义

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

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

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

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

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

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