二叉搜索树

上一讲提到的查找问题 , 分两类 : 静态查找 ( 查字典 )和动态查找 ( 经常发生插入删除 )

二分查找效率高 , 不用数组直接把元素放在树上 , 这样的树就是二叉查找树 ( 二叉搜索树 )
又称 BST , Binary Search Tree

性质

一颗二叉搜索树如果不空的话 , 满足以下性质 :

  • 非空左子树的所有键值小于其根结点的键值
  • 非空右子树的所有键值大于其根结点的键值
  • 左、右子树都是二叉搜索树

例 :
image.png

二叉搜索树操作的特别函数

  1. Position Find( ElementType X, BinTree BST) : 从二叉搜索树BST中查找元素 X , 返回其所在结点的地址
  2. Position FindMin( BinTree BST) : 从二叉搜索树BST中查找并返回最小元素所在的结点的地址
  3. Position FindMax( BinTree BST) : 从二叉搜索树BST中查找并返回最大元素所在的结点的地址
  4. BinTree Insert( ElementType X, BinTree BST) : 插入
  5. BinTree Delete( ElementType X, BinTree BST) : 删除

查找操作 Find函数

  1. Position Find(ElementType X, BinTree BST){
  2.     if( !BST ) return NULL;        /*如果不是BST类型则查找失败*/
  3.     if( X > BST->Data)
  4.         return Find(X, BST->Right);        /*在右子树中继续查找*/ /*尾递归*/
  5.     Else if( X < BST->Data)
  6.         return Find(X, BST->Left);        /*在左子树中继续查找*/ /*尾递归*/
  7.     else    /* X == BST->Data */
  8.         return BST;
  9. }

都是尾递归 : 在程序返回的时候才出现递归 (尾递归一般可以用循环实现)

  • 由于非递归函数的执行效率高 , 可将尾递归函数改为迭代函数
    Position IterFind(ElementType X, BinTree BST){
  while( !BST ) {
      if(X > BST->Data)
          BST = BST->Right;        /*向右子树中移动,继续查找*/
      else if( X < BST->Data)
          BST = BST->Left;        /*向左子树中移动,继续查找*/
      else        /* X == BST->Data*/
          return BST;        /*查找成功,返回结点的找到结点的地址*/
  }
  return NULL;    /*查找失败*/
}
    由此可知 : 查找的效率取决于树的高度
    **

查找最大和最小元素

  • 最大元素一定是在树的最右分支的端结点上
  • 最小元素一定是在树的最左分支的端结点上

例如 :
image.png

Position FindMin(BinTree BST){
    if( !BST ) return NULL;        /*空的二叉搜索树,返回NULL*/ 
    else if (!BST->Left)
        return BST;        /*找到最左叶结点并返回*/
    else 
        return FindMin(BST->Left);        /*沿左分支继续查找*/
}

查找最小元素的递归函数

Position FindMax( BinTree BST){
    if ( BST )
        while(BST->Right)    BST = BST->Right;    /*当右孩子不空时指针向右移动*/
                /*沿右分支继续查找,直到最右叶结点*/
    return BST;
}

查找最大元素的迭代函数

二叉搜索树的插入

分析 : 关键是要找到元素应该插入的位置 , 可以采用与Find类似的方法

image.png
需要注意的地方 : 上例中需要记住33的位置 , 需要递归函数返回到根结点的地址

BinTree Insert(ElementType X, BinTree BST){
    if(!BST){
                /*若原树为空,生成并返回一个结点的二叉搜索树*/
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else    /*开始找要插入元素的位置*/
        if(X < BST->Data)
            BST->Left = Insert(X, BST->Left);
                            /*递归插入左子树*/
        else if(X > BST->Data)
            BST->Right = Insert(X, BST->Right);
                            /*递归插入右子树*/
        /*else X已经存在,什么都不做*/
    return BST;                
}

二叉搜索树的插入算法

image.png

例

以一年十二个月的英文缩写为键值 , 按从一月到十二月顺序输入 , 即输入序列为 (Jan Feb…), 按字典顺序排列

image.png

二叉搜索树的删除

先找到再删除 , 找到之后考虑三种情况 :

  • 要删除的是叶子结点 : 直接删除 , 并再修改其父节点指针 —- 置为NULL
  • 要删除的是只有一个孩子的结点 : 将其父结点的指针指向要删除结点的孩子结点 (删除Aug : 将Apr指向Dec)
  • 要删除的是有左右两颗子树的结点 : 用另一个结点代替被删除的结点 , 右子树的最小元素或左子树的最小元素

取右子树的最小元素代替 :
image.png => image.png

取左子树的最小元素替代 :
image.png => image.png

BinTree Delete(ElementType X, BinTree BST){
    Position Tmp;
    if(!BST)    printf("要删除的元素未找到");
    else if(X < BST->Data)    /*判断根节点是否是删除目标元素*/
        BST->Left = Delete(X, BST->Left);    /*左子树递归删除*/
    else if(X > BST->Data)
        BST->Right = Delete(X, BST->Right);    /*右子树递归删除*/
    else    /*找到要删除的结点*/
        if(BST->Left && BST->Right){    /*被删除结点有左右两个子结点*/
            Tmp = FindMin(BST->Right);    /*在右子树中找最小的元素填充删除结点*/
            BST->Data = Tmp->Data;
            BST->Right = Delete(BST->Data,BST->Right);    /*在删除结点的右子树中删除最小元素*/
        } else {    /*被删除结点有一个或无子结点*/
            Tmp = BST;
            if(!BST->Left)    /*有右孩子或无子结点*/
                BST = BST->Right;
            else if(!BST->Right) /*有左孩子或无子结点*/
                BST = BST->Left;
            free(Tmp);
        }
    return BST;
}

平衡二叉树

定义

搜索树的结点插入次序不同的话 , 会导致树的深度和平均查找长度ASL的不同
(平均查找长度ASL : 衡量查找效率的指标)
例 :
image.png
上图中(a)为自然月份序列 , (b)按 72538146 10 9 11 12 , (c)按月份字符串大小顺序(英文单词的字典顺序)
其中 :

  • ASL(a) = (1+2╳2+3╳3+4╳3+5╳2+6╳1)/12 = 3.5
  • ASL(b) = 3.0
  • ASL(c) = 6.5

树(b)效率最高 , 因为相比之下最**平衡**

平衡因子

左右两边怎样才能维持平衡 ?
两个指标 : 左右两边的高度差不多 ; 左右两边的结点数差不多

因此定义了 平衡因子 (Balance Factor, BF) :

( h和h分别为T的左右子树的高度 )

平衡二叉树 (Balaced Binary Tree) : ( AVL树 )

  • 空树 , 或者任一结点左右子树高度差的绝对值不超过 1 , 即 三 : 树(中) - 二叉搜索树、平衡二叉树 - 图11

例 :
image.png

高度

问题 : 平衡二叉树的高度能达到 log**n 吗 ?**

image.png (完全二叉树的高度为 log**n **)
讨论 : 设 n 是高度为 h 的平衡二叉树的最小结点数。
结点数最少时 :
image.png image.png

h = 3时 , 至少需要7个结点
image.png

( 与斐波那契数列一致 )
得到查找效率 :
image.png

平衡二叉树的调整

调整方式的选择取决于 破坏者与被破坏者的关系

右单旋

问题 : 插入时导致原本平衡的二叉树不平衡了 , 此时需要**调整

image.png
抽象成 :

  • “不平衡”的发现者是 Mar (-2) , “麻烦结点” Nov在发现者右子树的右边
  • 因此叫 RR插入 , 需要 RR旋转(右单旋)

image.png
B 上的所有结点都比A大比B小 , 所以挂在A的右子树上
**

具体例

如下二叉树。5 是被破坏者 , 15 是破坏者
image.png
插入 13 作为破坏者 :
image.png

左单旋

非根节点的左单旋
image.png**
抽象成 :

  • “发现者” 是 Mar (-2) , “麻烦结点” Apr 在发现者左子树的左边
  • 因此叫 LL插入 , 需要 LL旋转(左单旋)

image.png
**

具体例

LR旋转

image.png
抽象成 :

  • “发现者”是 May, “麻烦结点” Jan 在左子树的右边
  • 因此叫 LR插入 , 需要 LR旋转

image.png

RL旋转

image.png

例 : 是否是同一颗二叉搜索树的判别

题意理解

  • 给定一个插入序列就可以唯一确定一颗二叉搜索树。
  • 然而 , 一颗给定的二叉搜索树却可以由多种不同的插入序列得到句号

问题

对于输入的各种插入序列 , 判断他们是否能生成一样的二叉搜索树

输入输出样例

image.png

求解思路

两个序列是否对应相同搜索树的判别

方法 :

  1. 分别建两颗搜索树的判别方法 : 根据两个序列分别建树 , 再判别树是否一样
  2. 不建树的判别方法
  3. 建一棵树 , 再判别其他序列是否与该树一致 (选用这种方法)

不建树的判别方法

第一个数相同表示根结点相同 , 后面的序列可以分为比根结点大的 (右子树) 和比根结点小的 (左子树) ,
然后比较两个序列的左右子树是否完全相同 (按上述方法递归)

建一棵树 , 再判别其他序列是否与该树一致

思路 :

  1. 搜索树表示
  2. 建搜索树T
  3. 判别另一序列是否与搜索树T一致

1. 搜索树表示

经典结构 : 

typedef struct TreeNode *Tree;
struct TreeNode {
    int v;
    Tree Left, Right;    /*左右指针表示链表*/
    int flag;    /*用来判别另一序列是否与该树一致 - 如果某结点没被访问则flag为0,被访问过为1*/
};

2. 程序框架搭建

int main()
{ 对每组数据
    ◉ 读入N和L    /*N为结点个数,L为序列个数*/
    ◉ 根据第一行序列建树T
    ◉ 依据树T分别判别后面的L个序列是否能与T形成同一搜索树并输出结果

    return 0;
}

根据上述基本框架 , 可以得到需要设计的主要函数有 :

  • 读数据建搜索树T
  • 判别某一序列是否与T构成一样的搜索树

具体实现 : 

int main()
{    
    int N,L,i;
     Tree T;

     scanf("%d",&N);
    while(N){
        scanf("%d",&L);
        T = MakeTree(N);
        for(i=0;i<L;i++){    /*后面有L个序列*/
            if(Judge(T,N))    printf("Yes\n");
            else    printf("No\n");
            ResetT(T);    /*清除T中的标记flag*/
        }
        FreeTree(T);
        scanf("%d",&N);
    }
     return 0;
}

3. 如何建搜索树

Tree MakeTree( int N ){    /*N为结点数*/
    Tree T;
    int i,V;

    scanf("%d",&V);
    T = NewNode(V);
    for(i=1;i<N;i++){
        scanf("%d",&V);
        T = Insert(T,V);    /*把当前读入的结点插到树里*/
    }
    return T;
}

Tree NewNode( int V ){
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->V = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}

Tree Insert( Tree T, int V){
    if(!T)    T = NewNode(V);
    else{
        if(V>T->v)
            T->Right = Insert(T->Right,V);
        else
            T->Left = Insert(T->Left,V);
    }
    return T;
}

4. 如何判别

image.png
如何判别序列 3 2 4 1 是否与树 T 一致 ?
方法 : 在树 T 中按顺序搜索序列 3 2 4 1 中的每个数

  • 如果每次搜索所经过的结点在前面均出现过 , 则一致
  • 否则 ( 某次搜索中遇到前面未出现的 ) , 则不一致 ```c int check(Tree T, int V){ /在树T中查找整数V/ if( T->flag){
      if(V<T->v)    return check(T->Left,V);
  else if(V>T->v)    return check(T->Right, V);
  else return 0;
    } else{
      if(V==T->v){
      T->flag = 1;
      return 1;
  }
  else return 0;
    } }

int Judge(Tree T, int N){ /有bug: 当发现序列中的某个数与T不一致时,必须把序列后面的数都读完/ int i,V;

scanf("%d",&V);
if(V!=T->v) return 0;
else T->flag = 1;

for(i=1;i<N;i++){
    scanf("%d",&V);
    if(!check(T,V)) return 0;
}

return 1;

}

int Judge(Tree T, int N){ /改写/ int i,V,flag = 0; /flag:0 代表目前还一致,1代表一定不一致/

scanf("%d",&V);
if(V!=T->v) flag=1;
else T->flag = 1;

for(i=1;i<N;i++){
    scanf("%d",&V);
    if((!flag)&&!check(T,V)) flag=1;
}
if(flag) return 0;
else return 1;

}


<a name="LgYHs"></a>
### 5. 小程序
```c
void ResetT( Tree T){    /*清除T中各结点的flag标记*/
    if(T->Left) ResetT(T->Left);    
    if(T->Right) ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T){    /*释放T的空间*/
    if(T->Left) FreeTree(T->Left);
    if(T->Right) FreeTree(T->Right);
    free(T);
}

课件

小白专场：是否同一棵二叉搜索树.pdf

小测验1: 二叉搜索树

image.png

课件1: 二叉搜索树

4.1 二叉搜索树.pdf

C语言实现: 二叉搜索树的插入与删除

BinTree Insert( BinTree BST, ElementType X )
{
    if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else { /* 开始找要插入元素的位置 */
        if( X < BST->Data )
            BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
        else  if( X > BST->Data )
            BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 

    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}