20 将疑犯加到搜索树中（第2/2页）

“我们不能加节点！”Socks大声说道。

“当然可以，”Frank说道，“往二叉搜索树中加节点很简单。从顶端开始，像寻找符合条件的值那样向下搜索。当你走到一个尽头时，把新的值加在它的下面就好了。

“我们以这个57天前的调职记录为例。我们从顶端开始，因为57大于根节点里面的55，所以我们向右走。接下来，因为57小于67，所以我们向左走。再接着，因为57小于61，所以我们再次向左走。现在比较57和59，我们应该再次向左走。但这个点并没有左子节点了。因此，我们将新的点加成59的左子节点就好了。”

Socks看起来被吓傻了。

“看，”Frank说道，“我再来给你演示一遍。这个调职记录是89天前的。89大于55，所以我们向右走；89大于67，所以又向右走；89大于85，因此再向右走。这里，因为89小于91，因此我们将它加成91的左子节点。”

“我不是这个意思，”Socks坚持道，“要是树变得不平衡了怎么办？”

“这的确有可能发生，”Frank承认道，“当你向二叉搜索树中添加元素的时候，树可能会变得不平衡。不过我们的搜索依然可以进行。”

“但是搜索在不平衡的树上会变得低效！”Socks抗议道。

“的确。”Frank承认道。

向树中添加节点的过程中，有时会抵消掉平衡二叉搜索树最大的优点之一——算法的高效率。将平衡二叉搜索树的节点数量翻倍时，它的层数只会增加1。这就意味着在搜索一个元素时，即使你将搜索数据的数量翻倍，你的搜索也只需要多进行一步。然而，Socks是对的：这种高效率只有在树左右平衡时才存在。在最坏的情况下，当树成为了一长条直线时，要找一个元素就必须沿着这条直线一直找下去了。而当我们向其中添加任意值的时候，不一定能保证树依然平衡。

“但这个险值得冒。”Frank最终这样说道。

“但是……”

“如果我们的搜索没有那么高效率，也没有关系。相比抱着那么多本子走过大半个城市来说，这只是一个很小的代价。那些本子看起来重极了。”

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

节选自Drecker教授讲义

向二叉搜索树中加入节点和寻找一个节点类似。我们从根节点开始逐步向下，操作就和我们寻找想加入的值一样。我们通过比较想加入的值和当前节点的值的大小，来决定是该向左下还是向右下走。当我们遇到死路时，也就是需要走的方向的子节点并不存在时，我们便将要加入的值插入到这个不存在的子节点的位置。

插入一个元素的计算量和树的深度成正比。但是，我们不能保证在插入新节点时依然可以保持树的平衡。事实上，当你按特定的顺序插入时，树很容易就会因为有很深的分支而变得不平衡。比如，如果我们按排好序的顺序来插入数字，所有这些加入的节点都会沿着一条分支排列。