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

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

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

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

考虑如下的二叉搜索树：

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

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

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

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

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