17 二叉搜索树陷阱

杰瑞米·库比卡提示您：看后求收藏（宜小说jmvip6.com），接着再看更方便。

在距离Cloaks andMore店不到一个街区的地方，Frank注意到有一个女人在跟踪他。即使十分恼怒，Frank也不得不承认她的跟踪技术很好。她一直走在街对面，在Frank后面至少30英尺的地方，她还时不时地通过商店窗户上的反光来观察Frank。并且她穿了一件没有任何特点的深绿色披风，这种颜色的披风在街上随处可见。

Frank突然停下来，弯下腰，假装自己在系鞋带。这是两种最常见的识别跟踪者的方法之一。另外一种则是突然向一个随意的方向快步走去，看看有谁会跟上来。虽然可能后者更加有效，但系鞋带这个动作动静更小，而且更重要的是，不需要人跑动。

跟踪者向前走过了Frank，却在前方十英尺的地方停了下来。她看起来仿佛在看一家玻璃透亮的商店里卖的卷心菜。

Frank站了起来，转身向反方向走去。过了半个街区，他横穿马路，愤怒的驴车驾驶员对他大喊大叫，Frank完全无视了他。Frank走到了马路的另一边，也就是跟踪者行走的一边。他随即向一个小巷中走去。一走进小巷，Frank便停了下来，开始等待。

当跟踪者匆忙跑过转角的时候，她几乎撞到了Frank身上。

“嗨，”Frank说道，“你为什么要跟着我？”他尽量让自己的语气平淡一些，但这在平时都是不可能的，这次虽然他没有尖叫，但语气还是像低吼一般。

职业密探一般都会花很长时间来计划如果被发现了该如何应对。他们有一大堆故事，用来在各种场合下圆场。他们甚至可以解释自己为什么会带着窃听装置和假乌龟出现在皇家宫殿中。他们的梦想就是能在这种情况下通过谎言来顺利过关。但现实一般不会如此顺利——他们经常会在意想不到的时候被发现。就像现在，Frank就希望能出其不意地抓住她。

但跟踪者异常专业，一点都没有紧张或者惊讶的迹象。她脸上露出了一丝愤怒，随后她丢下一颗烟雾弹，消失了。

就算她不丢烟雾弹，Frank也不可能追上她。在Frank反应过来准备去抓她的时候，她已经在街上跑远了。Frank咒骂了一声，穿过烟雾开始追她。

追了不到半个街区，Frank决定开始用深度优先搜索。这种情况下，密探一般都会尽快离开主路，试图逃离被追者的视线。大多数时候这都是一个很好的策略，但在这块几乎没有什么岔路的街区却明显行不通。

Frank边跑边将身边的街道想象成一个图。岔路口和死路的尽头是这个图上的点，而连接它们的路则是连接一个点与另一个点的边。

<img src="/uploads/allimg/200412/1-2004120PT4T2.jpg"/>

快速计算了一番后，Frank意识到在他落下太远之前，他只来得及搜索五六条岔路。这也是用深度优先搜索来追人所固有的缺陷。

Frank搜索完前两条街时一无所获。其中最像犯罪行为的便是一群孩子们在墙上涂鸦，他们用一根烧焦的木棍在墙上写了“递归之队”和“递归永恒”。Frank继续他的搜索。

又搜索过几条死路后，Frank正想着放弃，此时他在泥地中找到了一串通向一个打开的下水道口的脚印。他一边靠在墙上试图调整自己的呼吸，一边想着眼前的下水道肯定是她逃走的路。

Frank望向漆黑的下水道内，但什么都看不见。他爬进下水道，落在了一个木制平台上。他一边弯下腰，尽量让自己暴露的面积变小，一边巡视着这个房间。他所在的平台是固定在石墙上的，而它的下方是至少50英尺高的一间房子。唯一的一丝光是从头顶的下水道口照进来的，像一个位于远处的聚光灯一般。他看到那个密探从光照亮的椭圆形中跑过，跑向了对面的那堵墙。现在Frank已经被她甩掉很远了。

Frank思考着该如何选择。在他下面还有其他的平台，互相之间有20英尺的距离，并以铁梯子连接着。当他注意到地板上嵌着的黄铜标签时，他忍不住咒骂了一声：他现在正站在一个二叉搜索梯的顶端。

<img src="/uploads/allimg/200412/1-2004120PT4448.jpg"/>

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

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

<img src="/uploads/allimg/200412/1-2004120PT45a.jpg"/>

不幸的是，这种二叉搜索梯在艺术领域一直都未曾流行起来。这也许是因为它们体积太大了，而且还需要人不停地爬上爬下。不过很快它们就被犯罪分子们利用了起来。二叉搜索梯陷阱这种危险的东西是初级巫师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，所以他应该往左下方走。

<img src="/uploads/allimg/200412/1-2004120PT4236.jpg"/>

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

<img src="/uploads/allimg/200412/1-2004120PT4637.jpg"/>

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

<img src="/uploads/allimg/200412/1-2004120PT54R.jpg"/>

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

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

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

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

<img src="/uploads/allimg/200412/1-2004120PT5A1.jpg"/> <h2>警用算法导论：二叉搜索树Ⅰ</h2>

节选自Drecker教授讲义

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

<img src="/uploads/allimg/200412/1-2004120PT5O0.jpg"/>

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

<img src="/uploads/allimg/200412/1-2004120PT5K8.jpg"/>

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

<img src="/uploads/allimg/200412/1-2004120PT5357.jpg"/>

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

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

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