19 疑犯的二叉搜索树（第3/4页）

“我们把这种情况叫作搜索中的剪枝，”Notation补充道，“因为这就像从一棵树上面砍下了一个分支一样。”

当Frank看向她的时候，她想起来她不应该和Frank说话，便又沉默了。

“所以我们只要探索右边的分支就好。”Frank说道。

“递归着探索！”Socks补充道，听起来他简直太欢乐了。

“对，递归着探索，”Frank冷淡地同意道，“现在的节点上是38天。同样的，我们不需要将它加到结果列表中，并且我们也可以跳过它的左子树。”

“但我们需要递归探索它的右子树。”Socks说道。看起来他挺享受这个新的算法。

Frank点了点头。

下一个点没有子节点了。它已经是一条死路了。

“现在呢？”Socks问道。

“和深度优先搜索一样，”Frank说道，“我们倒退，并且选择之前还没有探索过的路线，直到我们将整棵树都搜索过了为止。因为我们一路上剪掉了很多分支，所以我们需要一直倒退到根节点。”

搜索接着在根节点的右子树里开始了。被找到的新记录被加入了结果列表，不合适的分支被一个个剪掉，而合适的分支则被递归地探索着。

最后他们找到了几条符合条件的调职记录。Frank仔细地研究了找到的结果，试图找出任何可疑的地方。

“什么都没有，”他难以置信地低吼了一声，“这里面什么都没有！”

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

节选自Drecker教授讲义

在二叉搜索树上进行区间查找和查找一个元素类似。算法从最顶端的根节点开始，一路递归着搜索整棵树。它根据以下三个条件来对在每一个节点做决定：

1.当前节点应该被算在结果中吗？如果当前节点在要找的区间内，我们就应该将它加到结果列表中。

2.应该探索左子树吗？如果当前节点有左子树，并且当前节点的值大于区间里最小值，我们就应该递归探索它的左子树。因为这种情况下，它的左子树可能包括区间内的值。

3.应该探索右子树吗？如果当前节点有右子树，并且当前节点的值小于区间里最大值，我们就应该递归探索它的右子树。因为这种情况下，它的右子树可能包括区间内的值。

使用二叉搜索树来做区间搜索的优势在于，可以通过剪去大量不可能包含要找的值的分支来减少计算量。

考虑如下的二叉搜索树：

如果想找在区间[8，20]内的所有值，你只需要访问全部25个节点中的7个（被访问的节点被标上了阴影）：

类似的，如果想找在区间[70，80]内的所有值，你只需要访问全部25个节点中的6个：

需要注意的是，访问一个节点不一定代表这个节点会被包括在最终结果列表里。在我们给出的两个例子中，可以看到算法也需要访问一些不在目标范围内的节点。之所以访问它们，是因为那些节点的子树可能包括我们想找的值。

和寻找一个值一样，用二叉搜索树做区间搜索只有在需要进行多次搜索时才高效。建立一棵二叉搜索树比搜索一遍数据需要更大的计算量。但是如果要搜索多次，这个计算量可以被均摊到多次搜索里，从而让每次搜索的平均计算量变小。

1. 1 剪枝，这是一个很形象的说法。在搜索算法优化中，就是通过某种判断，避免一些不必要的遍历过程。简单是说就是不用去遍历每个节点，形象点说就是剪去了搜索树中的某些肯定不需要考虑的“枝条”，故称剪枝。——译者注返回