第12章 二叉查找树(2)
12.2 二叉树的搜索
我们经常需要在二叉查找树查找某个key。除了查找（SEARCH）操作之外，二叉查找树也支持譬如最小值（MINIMUM），最大值（MAXIMUM），后继（SUCCESSOR）和前驱（PREDECESSOR）的查找。在本节，我们将会考查这些操作并且给出如何在高度为h的二叉查找树中，用O(h)时间内完成这些操作。
查找
我们使用下面的方法在二叉查找树中查找指定的key的结点。指定树的根结点root和键值k, TREE-SEARCH返回键值为k的指针，如果不存在k则返回NIL。
图12.2 搜索二叉查找树。要在树中查找key为13的结点，搜索路径为从树出发15->6->7->13。树中最小key值为2，它沿树根的left指针上可以找到。最大key值20，它沿树根的right指针上可以找到。结点key为15的后继是key为17的结点，因为key为17的结点是key为15结点的右子树上key最小的结点。Key为13的结点没有右子树，因此它的后继是它最低的祖先，该祖先的左孩子也是一个祖先。在本例中，key为15的结点是13的后继。
上面的方法从树根开始查找并沿树枝的路径向下搜索，如图12.2所示。每个遍历到地结点，它都会拿这结点的值跟目标对比，如两个值相等，搜索结束。如果k小于前结点的x->key,将会在x的左子树继续搜索，因为根据二叉查找树的性质表明了k不可能x的右子树中。同理，如果k大于前结点的x->key,将会在x的右子树继续搜索。递归遍历的结点形了一条由树根向下的路径。因此TREE-SEARCH运行时间是O(h),h为树的高度。
我们可以用while循环迭代“铺开”递归过程重写上面的算法。在大多数计算机中，这个算法的迭代版本会更高效一点。
最小值和最大值
在二叉查找树上，我们可以从根结点出发沿着结点的left指针直到某个结点的left为空，就可以找到二叉树中key最小的那个元素，如图12.2所示。下面的方法返回以指定结点x为根的二叉树中key最小的元素，假设x为非空。
二叉的性质保持TREE-MINIMUM方法是正确的。如果一个结点没有左子树，那么结点x的右子树上的所有结点的key都不小于x->key,那么根结点key肯定是它们当中的最小值。如果结点x有左子树，那么右子树上没有节点的key比x->key小并且左子树上的结点都不大于x->key,所以以x为根节点的子树上最小值一定在以左子树x->left为根的子树中。
同上，TREE-MAXIMUM方法的伪代码：
同TREESEARCH一样，上述的两个方法在高度为h的树中都要花费O(n),访问的结点形成了一条由根出的向上的一条简易的路径。
后继和前驱
给出一棵二叉查找树上指定的结点，有时候我们需要找到这个结点的中序遍历的顺序的后继。（译者注：二叉查找的中序遍历序列下是有序的）。如果所有结点的key都是不相同的结点x的后继是那些key大于x->key之中最小那个的结点。二叉树的结构特点，使我们不需要比较key就能找到指定结点的后继。下面的方法返回结点x的后继，如果x的key是二叉树中最大的则返回NIL。
我们在TREE-SUCCESSOR方法中的两种情况下退出返回。如果x结点的右子树非空，那么结点x的后继就是它右子树中最左那的结点，在第2行我们可看到调用了TREE-MINIMUM(x->right)。举个例子，在图12.2中key为15的结点后继是key为17的结点。
另一种情况，如练习12.2-6让你去实现的那样，如果x结点的右子树是空的并且x有祖先y，那y是x的祖先中最小的那个祖先，并且y的左孩子也是x的祖先。在图12.2中，key为13的结点的后继是key为15。为了找到y，我们简单的从x向上查找直到我们找到某个结点是双亲结点的左孩子为止；TREE-SUCCESSOR中第3到7行就为了处理这种情况。
TREE-SUCCESSOR在高为h的树上的运行时间是O(h)，因为我们是沿着树向上或者向下的一条简单的路径。TREE-PREDECESSOR,跟TREE-SUCCESSOR同理，运行时间也是O(h)。
即使所有key不都是完全相同，我们也把TREE-PREDECESSOR(x)返回结点作为x的前驱，TREE-SUCCESSOR(x)返回的作为后继。
总之，我们通过上面的叙述证明这样一个定理：
定理12.2 在高度为h的二叉查找树上，我们实现的动态集操作，SEARCH,MINIMUM,MAXIMUM，SUCCESSOR和PREDECESSOR运行时间都是O(h)。
练习
12.2-1 假设我们有一棵二叉查找树，元素值是都是在1到1000之间，我们想查找数字363.下面哪个查找序列不属于正确的访问序列。
a. 2, 252, 401, 398, 330, 344, 397, 363.
b. 924, 220, 911, 244, 898, 258, 362, 363.
c. 925, 202, 911, 240, 912, 245, 363.
d. 2, 399, 387, 219, 266, 382, 381, 278, 363.
e. 935, 278, 347, 621, 299, 392, 358, 363.
12.2-2 写出递归版本的TREE-MINIMUM和TREE-MAXIMUM
12.2-3 写出TREE-PREDECESSOR方法
12.2-4 Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点集合；B，搜索路径上的结点；C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a∈A，b∈B，c∈C一定满足a≤b≤c。对于上面的观点，请给出最小可能一个的反例。
12.2-5 证明：对于二叉查找树，如果一个结点有两个孩子，那么它的后继没有左孩子并且它的前驱没有右孩子。
12.2-6 二叉查找树T是没有重复key的集合。证明如果结点x的右子树为空并且x有后继y，那么y是x的最低祖先，并且y的左孩子也是x的祖先。（注意每个结点都是自己的祖先）。
12.2-7 有一种非常规的方法中序遍历n个结点的二叉查找树。通过TREE-MINIMUM找到最小元素然后通过n-1次调用TREE-SUCCESSOR。证明这种算法运行时间为O(n)。
12.2-8 证明不论从高度为h的二叉查找树的哪个结点开始，连续k次调用TREE-SUCCESSOR将花费O(k+h)时间。（译者注：前一次调用的结果作为后一次的调用参数）。
12.2-9 T是没有重复key的二叉查找树。如果x为它的一个叶子结点，y为x的双亲。证明y.key是T中大于x.key的集合中最小的或者y.key是T中小于x.key的集合中最大的。
全文下载:Chapter_12-Binary_Search_Trees
