算法导论（十二）－－二叉查找树

查找树（search tree）是一种数据结构，它支持多种集合操作，包括SEARCH，MINIMUM，MAXIMUM，PREDECESSOR，SUCCESSOR，INSERT和DELETE。

二叉查找树是用二叉树结构来组织的查找树。它满足这样的性质：每个结点的左子树中所有的元素都小于等于该结点的值，而该结点同时小于等于它的右子树中的所有元素的值。基于这个性质，只需一个中序遍历便可以按由小到大的顺序遍历树内的所有的元素：

INORDER_TREE_WALK(x) {
1      if x ≠ NIL {
2            INORDER_TREE_WALK(x.left);
3             print x.key;
4             INORDER_TREE_WALK(x.right);
5   }
}

其实从直观上，可以发现上面的代码就是遍历树中的所有的元素，所以它的运行时间为Ө(n)。但我们还是稍微证明下：
设根结点的左子树中元素个数为k，则其右子树中元素个数为n-k-1，所以：
T(n) = T(k) + T(n-k-1) + d　（d为常数，为访问一个元素的时间）
我们假设T(n) = c*n + d（这里取等于，不是大于或小于，可以同时求上界与下界），用代换法证明上式：
T(n) = (c*k+d) + (c*(n-k-1)+d) + d = c*n - c + 2*d
为使上式等于c*n+d，只需取c = d即可。

查询二叉查找树

下面的代码在二叉查找树中查找特定的关键字：

TREE_SEARCH(x, k) {
1      if x == NIL or x.key == k
2            return x;
3   if k < x.key
4            return TREE_SEARCH(x.left, k);
5      else
6            return TREE_SEARCH(x.right, k);
}

很明显，查找时会从根结点一直沿着某路径到达所要查找的元素或者叶结点，所以该算法运行时间为O(h)，其中h为二叉树的高度。

下面的代码是查找的非递归版本：

ITERATIVE_TREE_SEARCH(x, k) {
1      while x ≠ NULL and k ≠ x.key {
2            if (k < x.key)
3                  x = x.left;
4            else
5                  x = x.right
6      }
7      return x;
}

下面的代码找出二叉查找树的最小元素：

TREE_MINIMUM(x) {
1      while x.left != NIL
2            x = x.left
3   return x;
}

其实最小元素就是树的最左结点，这是一个从根到叶结点的一条路径，所以它的运行时间为O(h)。

下面找出最大元素：

TREE_MAXIMUM(x) {
1      while x.right != NIL
2            x = x.right;
3      return x;
}

它找出树的最右结点，运行时间也为O(h)。

我们同样可以找到某结点的前趋（predecessor）和后继（successor）（分别为刚好比该结点小和刚好比该结点大的两个结点）。

查找后继：

TREE_SUCCESSOR(x) {
1   if x.right ≠ NIL
2           return TREE_MINIMUM(x.right);
3   y = x.parent;
4      while y ≠ NULL and x ≠ y.left {
5            x = y;
6            y = y.parent;
7      }
9      return y;
}

如果一个结点有右子树，它的后继便是它右子树中的最小元素；如果它没有右子树，它的后继便是离它最近的并把它当成左子树部分的祖先。可以发现它不是从上往下查找便是从下往上查找，所以它的运行时间也为O(h)。
前趋也后继类似，它的运行时间也为O(h)。

插入与删除

插入时，从根开始向下查找，直到发现某结点，使得插入的元素可以作为叶结点直接成为该结点的子女，而不改变现有的其它元素的结构。

下面是插入的代码：

TREE_INSERT(T, z) {
1      x = NIL;
2      y = T.root;
3      while y ≠ NIL {
4            x = y;
5            if z.key ≤ y.key
6                  y = y.left;
7            else
8                  y = y.right;
9      }
10  if x == NIL // tree was empty
11          T.root = z;
12    else
13          if z.key ≤ x.key
14                x.left = z;
15          else
16                x.right = z;
}

插入时主要的操作也是查找，所以它的运行时间为O(h)。

删除一个元素要更复杂一些，因为我们在删除一个结点后，还要维护整棵树的二叉查找的性质。我们可以从三种情况考虑：

１、如果要删除的结点没有子女，那么可以直接把这个结点从树中删除；
２、如果要删除的结点只有一个孩子，则不论它是左孩子还是右孩子，用这个孩子代替被删掉的结点，（例如，要删除的结点是其父结点的右孩子，该结点只有一个左孩子，则使它的左孩子成为它的父结点的新的右孩子，再把要删除的结点从树中移除）；
３、如果要删除的结点有两个子女，则找到它的后继（右子树的最左结点）来代替这个被删除结点。（之所以这么做，因为它的后继比它的左子树的所有元素都大，又比它的右子树中的所有其它元素小。）

下面是删除的代码：

TREE_DELETE(T, z) {
1   if z.left == NIL or z.right == NIL
2            y = z;
3      else
4            y = TREE_SUCCESSOR(z);
5      if y.left ≠ NIL
6            x = y.left;
7      else
8            x = y.right;
9      if x ≠ NIL
10          x.parent = y.parent;
11    if y.parent == NIL
12          T.root = x;
13    else if y == y.parent.left
14          y.parent.left = x;
15    else
16          y.parent.right = x;
17    if y ≠ z {
18          z.key = y.key;
19          copy y's satellite data into z;
20    }
21    return y;
}

上面代码中，在第一种和第二种情况下（删除的结点没有子女或只有一个子女），y为要删除的结点，x为要删除的结点的孩子（可能为NIL）， 再把x代替y。在第三种情况下（删除的结点有两个子女），y为要删除的结点的后继，x只可能为该后继的右孩子，将后继的右孩子x代替该后继y，接着在第 17行，如果y≠z，则意味着情况三，需要用后继代替被删除的元素，但这里并不是通过改变父亲指针、子女的指针来代替，而是直接把后继的值拷贝到要删除的 元素中。

虽然要复杂些，但删除操作中结点替代的操作为常数，主要的性能消耗在对后继的查找中，所以删除操作的运行时间也为O(h)。

综上所述，二叉寻找树的所有操作，包括查找特定关键字、查找最大元素、查找最小元素、查找前趋、查找后继、插入和删除的运行时间都为O(h)，其中h为二叉寻找村的高度。

随机构造的二叉寻找树

通过前面的分析可以发现，二叉查找树的性能与树的高度密切相关。我们可以用随机选择插入元素的方式来获得一个好的期望性能：对于n个要插入的元素，每次随机选取其中一个插入，这种方式构造出来的二叉寻找树的期望高度为lg(n)。证明参考原书12.4节。