68-二叉排序树

1. 什么是二叉排序树

  二叉排序树(Binary Sort Tree，简称BST)又称二叉查找(搜索)树，其定义为：二叉排序树或者是空树，或者是满足以下性质（BST性质）的二叉树：

  1. 若它的左子树非空，则左子树的所有节点的值均小于根节点的值

  2. 若它的右子树非空，则右子树的所有节点的值均大于根节点的值

  3. 它的左，右子树本身又各是一棵二叉排序树。

注意：二叉排序树中没有相同关键字的节点。

图1-二叉排序树

  图1中的二叉树就是一棵二叉排序树，例如以66为根节点的二叉树中，其左子树中中的所有节点的值都比根节点小，而其右子树正好相反，同时我们还可以看到左，右子树又各是一棵二叉排序树。

  有小伙伴可能会想，如果有一颗二叉树的左，右子树各是一个二叉排序树，那么能否确定这是一棵二叉排序树？

图2-非二叉排序树

   对于上图中的这棵二叉树来说，就不是一棵二叉排序树，虽然左子树是一棵二叉排序树，但是对于值为50的根节点来说，其左子树中有一个值为66的节点比根节点的值要大，因此不满足二叉排序树的定义，也就是说，当一棵二叉树的左，右子树本身各是一棵二叉排序树的时候，这棵二叉树并不一定是一棵二叉排序树。

2. 二叉排序树的存储结构

二叉排序树的存储结构定义如下：

typedef struct node
{
    KeyType key;                        //关键字项
    InfoType data;                      //其他数据域
    struct node *lchild,*rchild;        //左右孩子指针
} BSTNode;

3. 二叉排序树的查找

   通常构造一棵二叉排序树是为了提高查找和插入删除的效率。比如在一个有序的数据集上查找的效率总是要高于无序的数据集，相对于普通的二叉树来说，二叉排序树的查找和插入删除效率明显要高的。

   在对二叉排序树查找时，我们可以将二叉排序树看做是一个有序表，所以在二叉排序树上进行查找，和二分查找是类似的，也是一个逐步缩小查找范围的过程，我们通过下面这个例子来说明二叉排序树的查找。

图3-二叉排序树的查找

  假设查找值为25的节点，而k的值就为25，首先从值为66的根节点开始比较，由于25的值比66要小，于是查找左子树，发现25还是比30这个值要小，于是继续查找左子树，发现25比20这个值要大，于是查找右子树，发现25和25正好相等，于是就找到了要查找的节点，有没有感觉这个查找过程和二分查找是比较类似的呢？

下面我们来看一下二叉排序树的查找算法：

//二叉排序树的查找算法
BSTNode *SearchBSTNode(BSTNode *bt , KeyType key)
{
    while (bt != NULL)
    {
        if(bt->key == key)
        {
            return bt;
        }

        if(bt->key > key)
        {
            bt = bt->lchild;
        }
        else
        {
            bt = bt->rchild;
        }
    }
    return NULL;
}

二叉排序树的查找递归版实现：

//二叉排序树的查找算法递归版
BSTNode *SearchBSTNode2(BSTNode *bt , KeyType key)
{
    if(bt == NULL || bt->key == key)
    {
        return bt;
    }

    //查找左子树
    if(bt->key > key)
    {
        return SearchBSTNode(bt->lchild , key);
    }
    //查找右子树
    else
    {
        return SearchBSTNode(bt->rchild , key);
    }
}

  通过二叉树的查找我们可以发现，当以中序方式对二叉排序树进行遍历时发现，最后得到的是一个有序的遍历序列。

4. 二叉排序树插入操作

  在二叉排序树T中插入一个关键字为k的新记录，要保证插入后仍满足BST性质。二叉排序树的插入过程：

（1）若二叉排序树T为空，则创建一个key域为k的节点，将它作为根节点；

（2）否则将k和根节点的关键字比较
  若k和根节点相等，则说明树中已有此关键字k，无须插入，直接返回0；
  若kkey，则将k插入根节点的左子树中；
  否则将它插入右子树中

//二叉排序树的插入操作
int InsertBSTNode(BSTNode *&bt , KeyType key)
{
    if(bt == NULL)
    {
        bt = (BSTNode *)malloc(sizeof(BSTNode));
        bt->data = 0;
        bt->key = key;
        bt->lchild = NULL;
        bt->rchild = NULL;

        return 1;
    }

    if(bt->key == key)
    {
        return 0;
    }
    else if(bt->key > key)
    {
        return InsertBSTNode(bt->lchild , key);
    }
    else
    {
        return InsertBSTNode(bt->rchild , key);
    }

}

需要注意的是：任何节点插入到二叉排序树时，都是以叶子节点插入的。

5. 二叉排序树的查找性能分析

图4-二叉排序树的查找性能

   现在有这样的一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}，求在等概率的情况下查找成功的平均查找长度。

   于是可以把每一层需要查找的个数全部都算一遍，例如：第一层需要比较的节点有一个，第二层需要比较的节点有两个，第三层需要比较的节点有三个，第四层需要比较的节点也有三个，第五层需要比较的节点有两个，第六层需要比较的节点有一个。

平均查找长度如下：

ASL成功=1×1+2×2+3×3+3×4+2×5+1×612=3.5$AS{L}_{成功}=\frac{1\times 1+2\times 2+3\times 3+3\times 4+2\times 5+1\times 6}{12}=3.5$

那么对于不成功的概率，我们把所有不成功的情况都列出来，如下图所示：

图5-二叉排序树的查找性能

其平均查找长度为：

ASL不成功=1×2+3×3+4×4+3×5+2×613=4$AS{L}_{不成功}=\frac{1\times 2+3\times 3+4\times 4+3\times 5+2\times 6}{13}=4$

  对于二叉树的查找，通常是从根节点开始查找的，且查找比较的次数等于给定值的节点在二叉排序树的层数，极端情况下根节点就是我们要查找的关键字，只需查找一次，最多也不会超过树的深度。换句话说，二叉排序树的查找性能是非常依赖于二叉排序树的形状，然而现实是二叉树的形状通常是不确定的。

图6-二叉排序树的形状

  例如现在有这样的一组关键字{2,4,11,18,25,32,39,46,53,60,67,74}，按顺序依次插入到一棵初始为空的二叉排序树中，就会形成上图中的一棵只有右子树的，极端二叉排序树，但它依然是一棵二叉树。

它的平均查找长度为：

ASL成功=1×1+1×2+1×3+1×4+1×5+1×6...+1×1212=6.5$AS{L}_{成功}=\frac{1\times 1+1\times 2+1\times 3+1\times 4+1\times 5+1\times 6...+1\times 12}{12}=6.5$

  而对于这种极端，不平衡的二叉排序树来说，它的查找性能通常是非常糟糕的，因此我们需要将这种极端的二叉排序树转换为一种平衡的二叉树来提高查找效率。

6. 二叉排序树的删除

  第一种情况：二叉排序树的节点删除操作，对于被删除的节点是叶子节点的话，直接删除该节点即可。

图7

  例如，在删除关键字为20的节点时，需要将其关键字为30的双亲节点的指针（左孩子指针）值置为空就行。当要删除关键字为88的节点时，同理，将其双亲节点85的指针（右孩子指针）值置为空。

  第二种情况：当被删除的节点只有左子树，用其左子树代替；只有右子树，用其右子树代替它。

图8

  例如，当要删除关键字为40的节点，该删除的节点只有左子树，那么将该节点的双亲节点（关键字为30）的相应指针域的值改为指向被删除节点的左子树。又或者删除关键字为80的节点只有右子树，那么将其双亲节点（关键字为50）的相应指针域的值改为被删除节点的右子树。

第三种情况：被删除的节点既有左子树，也有右子树。

图9

  二叉排序树以中序遍历得到的是一个有序的遍历序列，假设要删除关键字为50的节点，那么它的前驱是左子树中最大的节点（关键字为40），以前驱节点代替之，然后再删除该前驱节点。

图10

  同理，后继节点是右子树中最小的节点，也可以用被删除的节点的后继节点（关键字为80）代替之，然后再删除该后继节点。

7. 二叉排序树的删除算法

  关于二叉排序树的删除操作已经介绍完了，这里啰嗦一下，如果你已经非常明白二叉排序树的删除过程的话，那么二叉排序树的删除算法对你来说，应该不难。

//Delete1算法用于删除左，右子树都不为空的情况
void Delete1(BSTNode    *p,BSTNode  *&r)
{
    BSTNode *q;
    //一直往右找
    if (r->rchild!=NULL)
        Delete1(p,r->rchild);
    else
    {
        //把节点更改为找到的节点
        p->key=r->key;
        //记录找到的节点
        q=r;
        //将找到节点的左孩子节点替代找到的节点
        r=r->lchild;
        //将找到的节点释放
        free(q);
    }
}


void Delete(BSTNode *&p)
{
    BSTNode *q;
    //没有右子树的情况
    if (p->rchild==NULL)
    {
        //记录要删除的节点
        q=p;
        //左子树替代要删除的节点（双亲节点）
        p=p->lchild;
        //释放要删除的节点
        free(q);
    }
    //没有左子树的情况
    else    if (p->lchild==NULL)
    {
        q=p;
        p=p->rchild;
        free(q);
    }
    //有左，右子树的情况
    else    
Delete1(p,p->lchild);
}

int DeleteBST(BSTNode*&bt , KeyType k)
{
    if (bt==NULL)
        return 0;
    else
    {
        if (k<bt->key)
            return DeleteBST(bt->lchild,k);
        else    if (k>bt->key)
            return DeleteBST(bt->rchild,k);

        //找到了要删除的节点
    else
        {
Delete(bt);
            return 1;
        }
    }
}