二叉排序树

二叉排序树

二叉排序树(Binary Sort Tree)或者是一棵空树，或者是具有如下性质的非空二叉树：
(1) 若其左子树不空，则左子树上所有节点的值均小于它的根节点的值；
(2) 若其右子树不空，则右子树上所有节点的值均大于它的根节点的值；
(3) 其左、右子树也分别是二叉排序树。

可见，二叉排序树是一个递归的数据结构，可以方便地使用递归算法对二叉排序树进行各种运算。此外，根据定义可知

$$ 左子树节点值 < 根节点值 < 右子树节点值 $$

因此，对二叉排序树进行中序遍历，可以得到一个递增的有序序列，序列中不存在相等的元素。

二叉排序树的查找

二叉排序树（查找树）的查找从根节点开始，沿着某一分支向下进行比较。
若二叉排序树非空，先将给定值与根节点关键字比较，若相等则成功；
若不等，当给定值小于根节点关键字时，在根节点左子树中查找；
否则，当给定值大于根节点关键字时，在根节点右子树中查找；
显然，这是个递归的过程。
用二叉链表作为二叉排序树的存储结构，则该查找过程的算法实现如下：

BSTree SearchBST_Recursion(BSTree T, TElemType key)
{
    if (T == NULL || key == T->data) return T;
    else if (key < T->data) return SearchBST(T->lchild, key);
    else return SearchBST(T->rchild, key);
}

也可以用非递归来实现：

BSTree SearchBST_Non_Recursion(BSTree T, TElemType key)
{
    BSTNode *p = T;
    while (p && p->data != key)
    {
        if (key < p->data) p = p->lchild;
        else p = p->rchild;
    }
    return p;
}

二叉排序树的插入

二叉排序树是动态查找表，它的树结构通常不是一次性生成的，而是在查找过程中，当树中不存在关键字值等于给定值的节点时再进行插入。
新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上最后一个访问的节点的孩子节点

可见，插入过程也需要进行查找，可以到待查值时，则返回所得节点；没有找到时，ze返回最后一个访问的节点，以便进行后续插入
为了能在查找失败时，返回最后一个访问的节点，在查找过程中需要一个指针 f 记录一下上一个访问的节点，即当前访问节点的双亲，起始 f = NULL。

因此，对之前的查找进行修改，增加一个指针 f 指向上一个访问的节点（双亲）

// 返回值修改为布尔量，标识是否找到待查值，由 p 指向返回的节点
Status SearchBST_Non_Recursion(BSTree T, TElemType key, BSTree *p)
{
    BSTNode *f = NULL, *t = T;
    while (t && key != t->data)
    {
        f = t;
        if (key < t->data)  t = t->lchild;
        else t = t->rchild;
    }
    if (t) { (*p) = t; return 1; } // 找到
    else { (*p) = f; return 0; } // 未找到
}

于是二叉排序树的插入算法如下：

Status InsertBST(BSTree *T, TElemType key)
{
    BSTNode *p, *s;
    if (0 == SearchBST_Non_Recursion(*T, key, &p))
    {
        // 生成新结点
        s = (BSTNode *)malloc(sizeof(BSTNode));
        s->data = key; s->lchild = s->rchild = NULL;
        // 插入
        if (p == NULL) (*T) = s; // 空树
        else if (key < p->data) p->lchild = s;
        else p->rchild = s;
        return 1;
    }
    else
        return 0;
}

二叉排序树的构造

二叉排序树是动态查找表，构造一棵二叉排序树就是不断插入新节点的过程，因此**二叉排序树中一定没有相同元素，**这符合二叉排序树的定义。
根据二叉排序树性质，中序遍历可以得到一个递增的有序序列，也就是说一个无序序列可以通过构造二叉排序树变成一个有序序列，构造树的过程也就是排序过程。
因为插入操作均发生在叶子节点，它不需要移动其他节点，只需要修改指针，这就相当于在有序序列上插入一个新元素却不需要移动其他元素，
可见，二叉排序树既能像顺序表一样进行折半查找（类似），又能进行链式结构的插入操作，不需要大量移动元素，因此二叉排序树是动态查找表一种经典实用的表示方式。

// 通过节点插入新建一棵二叉树
Status InitBST(BSTree *T, TElemType *key, int n)
{
    int i;
    (*T) = NULL;
    for (i = 0; i < n; ++i)
    {
        InsertBST(T, key[i]);
    }
    return 1;
}

二叉排序树的删除

在二叉排序树中删除一个节点时，不能把以该节点为根的子树上的所有节点都删除，只能删除这个节点本身，然后将其断开的子树重新链接到原来的排序上，并且要确保重新链接的排序树的性质特性不会丢失。
二叉排序树的性质与中序遍历序列紧密相关，因此要确保重新链接的排序树特性不丢失，可以从中序遍历的角度思考，即用删除节点的中序前驱或后继顶替她原本的位置即可。

具体地，有如下三种情形：
(1) 被删除节点 p 是叶子节点，则直接删除即可；
(2) 被删除节点 p 只有左或右子树，则让它的子树顶替它的位置，即让它的子树链接到它的双亲；
(3) 被删除节点 p 有左、右子树，则让它的直接中序前驱或后继顶替它的位置，然后删除该前驱或后继；

(Ⅰ) 用前驱顶替，即用其左子树最右下节点 s 顶替 p，由于 s 没有右子树，所以只需再将 s 的左子树链接到 s 的双亲上，最后删除 s；
处理一个特殊情形：p 的左孩子就是其前驱 s，即 p 的左孩子没有右子树，这是(2)的场景，按(2)处理即可；
(Ⅱ) 用后继顶替，即用其右子树最左下节点 s 顶替 p，由于 s 没有左子树，所以只需再将 s 的右子树链接到 s 的双亲上，最后删除 s；
处理一个特殊情形：p 的左孩子就是其前驱 s，即 p 的右孩子没有左子树，这是(2)的场景，按(2)处理即可；

可见，前驱顶替和后继顶替的操作是刚好对称的。

除了用直接前驱或后继替换外，还有其他思路也能完成删除操作，譬如

将待删除节点 p 的左子树链接到它的双亲 f 顶替自己，而将 p 的右子树链接到 p 直接前驱 s，作为 s 的右子树。

根据中序操作的对称性，也可以用右子树顶替自己。

技巧：在进行子树或节点移动使，可以直接将子树当作节点处理，原因在于二叉排序树是一个递归结构，排序子树的内部结构不会因为（其双亲）根节点被删除而破坏。

void Delete(BSTree *p)
{
    BSTNode *q, *s;
    // 右空用左顶替
    if ((*p)->rchild == NULL)
    {
        q = (*p); (*p) = (*p)->lchild; free(q);
    }
    // 左空用右顶替
    else if ((*p)->lchild == NULL)
    {
        q = (*p); (*p) = (*p)->rchild; free(q);
    }
    // 左右都不空
    else
    {
        q = *p; s = (*p)->lchild;
        // 左子树右下找前驱
        while(s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        // s 顶替 p
        (*p)->data = s->data;
        // 处理特殊情形
        if (q == (*p))
            q->lchild = s->lchild;
        // 处理一般情形
        else
            q->rchild = s->lchild;
        free(s);
    }
}

另一种思路：(2)(3)可以合并

void Delete_2(BSTree *p)
{
    BSTNode *q, *s;
    if ((*p)->rchild == NULL)
    {
        q = (*p); (*p) = (*p)->lchild; free(q);
    }
    else
    {
        // 左树右下找 p 的前驱 s
        q = (*p); s = (*p)->lchild;
        while(s->rchild)
            s = s->rchild;
        // (*p) 的右子树作为 s 的右子树
        s->rchild = (*p)->rchild;
        // (*p) 的左孩子顶替自己
        (*p) = (*p)->lchild;
        free(q);
    }
}

关于删除再插入的问题：
如果在二叉排序树中先删除再插入一个节点，得到的排序树是否与原来相同？
答案是不一定！！原因在于删除操作可以发生在叶子节点和非叶子节点，而插入操作只发生在叶子节点，如果删除和插入的位置不同，得到的树也一定与之前不同。
当被删除节点是非叶子节点，那么重新插入时该节点就成了叶子节点，显然前后两个二叉树不一样；
但是，还需要注意的是，虽然树结构不同，但是中序序列是相同的，这是由二叉排序树的特性决定的。

二叉排序树的查找分析

和折半查找类似，二叉排序树的进行查找比较的次数不超过树的深度 h，不过折半查找长度为 n 的表的判定树是唯一的，而含有 n 个节点的二叉排序树却不是唯一的，相同的关键字插入的顺序（时间点）不同就可能生成不同的二叉排序树。

因此不同的二叉排序树，它的平均查找长度也就不同。也就是说，含有 n 个节点的二叉排序树，它的平均查找长度和树的形态有关。

最坏的情况下，先后插入的关键字有序时，构造出的二叉排序树就蜕变成一棵单支树，树的深度增加为元素数量 n，平均查找长度为 \(\frac {n+1}{2}\)；
最好的情况下，二叉排序树的形态和折半查找判定树相同，这时平均查找长度和 \(\log_2 n\) 成正比。

随机的情况下，二叉排序树的平均查找长度和 \(\log_2 n\) 是等数量级的，但在某些情况下，尚需要在构成二叉排序树的过程中进行“平衡化”操作，得到二叉平衡树。

与折半查找对比（二分查找）：

就维护查找表的有序性而言，二叉排序树进行插入和删除时，不需要移动节点，只需要修改指针，平均执行时间为 \(O(\log_2 n)\)；
折半查找的存储结构是顺序表，进行插入和删除时，需要（大量）移动节点，需要的代价时 \(O(n)\)。

静态查找表，宜采用顺序表作为存储结构，使用折半查找策略；
动态查找表，宜采用二叉排序树作为逻辑结构。