第12章 二叉搜索树

12.1、二叉搜索树

二叉搜索树，使用一个链表数据结构来表示结点。每个结点是一个对象，包含属性key、left、right、p，分别代表其值、左孩子、右孩子和父节点。
子结点或父节点不存在时，属性值为NIL。
根节点是树中唯一父指针为NIL的结点。

二叉搜索树的性质：
二叉搜索树的每个结点，都满足其左子树上的结点都小于等于该节点的值，其右子树上的结点都大于等于该节点的值。

定理 12.1：
一棵有n个结点的树，使用中序遍历法需要 O(n)时间。

12.2、查询二叉搜索树

查找

在二叉搜索树上的查询的运行时间为O(h)，其中h为树的高度。
其搜索伪代码如下：

 TREE-SEARCH(x, k)
 if x == nil or k == x.key
     return x;
 if k < x.key
     return TREE-SEARCH(x.left, k);
 else
     return TREE-SEARCH(x.right, k);

最大关键字搜索和最小关键字搜索

搜索最小关键字的伪代码：

TREE-MINIMUM(x)
while x.left 不等于 nil
    x = x.left;
return x;

对称的，搜索最大关键字的伪代码：

TREE-MAXIMUM(x)
while x.right 不等于 nil
    x = x.right;
return x;

这两种查询的运行时间都是O(h)，其中h为树的高度。

后继和前驱

按照中序遍历法，获取一个节点的后继的伪代码：

TREE-SUCCESSOR(x)
if x.right不等于nil
    return TREE_MINIMUM(x.right);
y = x.p;
while y 不等于NIL, and x == y.right
    x = y;
    y = y.p;
return y;

说明：

1. 节点x的右子树非空，那么其后继就是右子树中最小的结点；
2. 结点x的右子树为空，并有一个后继，那么这个后继就是结点x的有左孩子的最底层（最靠近根节点）的祖先，该后继也是结点x的祖先。

按照中序遍历法，获取一个节点的前驱的伪代码：

TREE-PREDECESSOR(x)
if x.left 不等于 nil
    return TREE-MAXIMUM(x.left);
y = x.p;
while y 不等于nil and x == y.left
    x= y;
    y = y.p; 
return y;

12.3、插入和删除

插入

TREE-INSERT(T,z)
y = nil;
x = T.root;
while (x 不等于 nil)
    y = x;
    if z.key < x.key
        x = x.left;
    else
        x = x.right;
z.p = y;
if y == nil
    T.root = z;
else
    if y.key <= z.key
        y.right = z;
    else
        y.left = z;

说明：

• 遍历过程中，y是记录z的父节点位置；
• while循环中向右或向左移动，向下遍历寻找z的应该插入的位置，即x为nil的位置，此时记录x的父节点y；
• 最后，设置新节点z的父节点，并设置z为父节点的左子节点或右子节点。

删除

二叉树删除子节点z的几种情况：

1. z没有左孩子，就直接用右孩子来替换z。右孩子可以是nil，也可以不是nil。
2. z有左孩子，并且只有这一个孩子，就直接用左孩子来替换z。
3. z既有左孩子，又有右孩子。这时，要在z的右子树中寻找z的后继y。这个后继y肯定没有左孩子。那么这种情况又分为两种：y是z的右孩子和y不是z的右孩子
   3.1. 后继y，是z的右孩子，就直接用y替换z，继续保留y的右孩子（y是没有左孩子的）。
   3.2. 后继y，在z的右子树中，但是不是z的右孩子。这种情况下，先用y的右孩子替换y的位置（y没有左孩子），再用y替换z的位置。

这个过程中，涉及到移动子树，因此要先定义一个移动子树的过程TRANSPLANT。主要是要替换树的父节点
在树T中，用子树v替换子树u，移动子树的伪代码：

TRANSPLANT(T, u, v)
    if u.p == nil
        T.root = v;
    else if u == u.p.left
        u.p.left = v;
    else
        u.p.right = v;
    if v != nil
        v.p = u.p;

利用TRANSPLANT移动子树的过程，从二叉搜索树中删除节点z的伪代码：

TREE-DELETE(T,z)
    //对应z没有左孩子节点
    if z.left == nil
        TRANSPLANT(T, z, z.right);
    //对应z有左孩子节点，但是没有右孩子节点
    else if z.right == nil
        TRANSPLANT(T, z, z.left);
    else
        //对应z既有左孩子节点，又有右孩子节点，先去右子树中找z的后继
        y = TREE-MINIMUM(z.right);
        //对应后继y不是z的右孩子，用y构建z的父节点的子树
        if y.p != z
            TRANSPLANT(T, y, y.right)
            y.right = z.right;
            y.right.p = y;
        //对应后继是z的右孩子的情况，直接用z的右孩子替换z的位置
        TRANSPLANT(T, z, y)
        y.left = z.left;
        y.left.p = y;

插入和删除的运行时间均为O(h)，h为树的高度 **

12.4、随机构建二叉搜索树

随机构建二叉搜索树定义如下：
按随机次序插入n个关键字到一棵初始空树中，从而生成的树。

一棵n个不同关键字的随机构建二叉树的期望高度为O(lg n);**