二叉排序树（BST）_关键字序列构造二叉排序树

• 二叉排序树的定义
• 查找操作
• 插入操作
• 删除操作
• 查找效率分析——平均查找长度ASL
• 平衡二叉树（二叉排序树的引申概念）

二叉排序树的定义

二叉排序树，又称二叉查找树（BST，Binary Search Tree）

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

1、左子树上所有结点的关键字均小于根结点的关键字；

2、右子树上所有结点的关键字均大于根结点的关键字。

左子树与右子树各是一棵二叉排序树。

左子树结点值<根结点值<右子树结点值

如果对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

 二叉排序树可以用于元素有序组织、搜索。

---

二叉排序树的查找

若树非空，目标值与根结点的值比较：

1、若相等，则查找成功；

2、若小于根结点，则在左子树上查找，否则在右子树上查找。

查找成功，返回结点指针；查找失败返回NULL。

 例1：查找关键字为30的结点。

从根结点出发，我们要找的值30>根结点19，根据排序树的特性，要找的结点一定在右子树中。

让指向根结点的指针，往根结点的右孩子方向走，指向50，30<50；

让指向50的指针，往50的左孩子方向走，指向26，30>26；

让指向26的指针，往26的右孩子方向走，指向30，找到结点。

//二叉排序树结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
 
//在二叉排序树中查找值为key的结点（非递归实现）
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){            //若树空或等于根结点值，则结束循环
        if(key<T->key)    T=T->lchild;      //小于，则在左子树
        else T=T->rchild;                   //大于，则在右子树
    }
    return T;
}
 
//在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
        return NULL;        //查找失败
    if(key==T->key)
        return T;           //查找成功
    else if(key<T->key)
        return BSTSearch(T->lchild,key);    //在左子树中查找
    else
        return BSTSearch(T->rchild,key);    //在右子树中查找
}

非递归算法：最坏空间复杂度O(1)

递归算法：最坏空间复杂度O(h)        //h为树的高度

---

二叉排序树的插入

若原二叉排序树为空，则直接插入结点；

否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。

//在二叉排序树插入关键字为k的新结点（递归实现）
int BST_Insert(BSTree &T,int k){
    if(T==NULL){                    //原树为空，新插入的的结点为空结点
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;                   //返回1，插入成功
    }
    else if(k==T->key)              //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<T->key)               //插入到T的左子树
        return BST_Insert(T->lchild,k);
    else                            //插入到T的右子树
        return BST_Insert(T->rchild,k);
}

传入引用类型参数，因为要修改右孩子指针。

二叉树不允许任意两个结点值相等，所以当k==T->key时，插入失败，return 0。

新插入的节点一定是叶子结点。

递归实现二叉排序树的插入算法，最坏时间复杂度为O(h)。

二叉排序树的构造

例1：按照序列 str = { 50,66,60,26,21,30,70,68 } 建立BST

//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;                //初始时T为空树
    int i=0;
    while(i<n){            //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

例2：按照序列 str = { 50,26,21,30,66,60,70,68 } 建立BST

        例1和例2，构造的二叉排序树相同，如下图所示：

        

结论：不同关键字序列，可能得到相同的二叉排序树，也可能得到不同的二叉排序树（如，例3)。

例3：按照序列 str = { 26,21,30,50,60,66,68,70 } 建立BST

        例3构造的二叉排序树，如下图所示：

        

---

二叉排序树的删除

先搜索目标结点：

1、若被删除的结点z是叶子结点，则直接删除，不会破坏二叉排序树的特性。

（二叉排序树的特性：左子树结点值<根结点值<右子树结点值）

2、若结点z只有一棵左子树或右子树，则让z的子树，替代z的位置。

3、若结点z既有左子树又有右子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

 【第三种情况说明】：结点z既有左子树，又有右子树，如50这个结点。

删去50这个结点后，需要有结点来替代这个位置，以保证二叉排序树的特性。

• 第一种方法：用z的直接后继替代z。找到z的右子树当中，值最小的结点，替代结点z。

       值最小的结点：就是z的右子树当中，按照中序遍历，第一个被访问的结点。

     （因为：二叉排序树的中序遍历序列，是一个递增的有序序列）

       z的直接后继：z的右子树中最左下的结点。

       让结点60替代结点50，删除原来的60（转成第二种情况，用60的右子树替代60）。

       

       以上是第一种方法，用z的直接后继替代z。

• 第二种方法：用z的直接前驱替代z。找到z的左子树当中，值最大的结点，替代结点z。

        值最大的结点（z的直接前驱）：左子树中，最右下的结点。

       

       让结点30替代结点50，删除原来的30（转成第一种情况）。

       

---

 查找效率分析

查找长度——在查找运算中，需要对比关键字的次数，称为查找长度，反映了查找操作时间复杂度。

提出概念：平均查找长度ASL（Average Search Length），用来评估整棵排序树的查找效率。

• 查找成功的平均查找长度：

 如果找的是50这个结点，显然只需要对比关键字一次，就可以查找成功；

如果要找26或66这两个结点，需要对比两次；

如果要找的是第三层这几个结点，就要对比三次；

第四层结点需要四次对比。

查找树中任何一个结点的概率都是等可能的，所以目标结点是其中任意一个结点的概率是1/8。

所以，查找成功的平均查找长度ASL=（1*1+2*2+4*3+1*4）/ 8=2.625

• 查找失败的平均查找长度：

如果查找失败，扫描指针只可能出现在叶子结点的空链域上，总共有9种情况是查找失败的，概率是1/9。

如果扫描指针停在第三层，则需要对比3次；（7*3）

如果扫描指针停在第四层，则需要对比4次。（2*4）

ASL=（7*3+2*4）/ 9 = 3.22

二叉排序树的查找效率，很大程度上取决于树的高度。

最好情况：n个结点的二叉树最小高度为[log n]+1。平均查找长度=O(log n)。

最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)。

左、右子树高度差越小，查找效率越高。

引申出新的概念——平衡二叉树。

---

平衡二叉树

平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。

如果能保持平衡，就意味着这棵二叉排序树的高度，或者说平均查找长度，可以到达O(log n)。