平衡二叉树_如何防止二叉树出现退化解-CSDN博客

本文链接：https://blog.csdn.net/ACM_hades/article/details/89925623

排序二叉树的退化：

上一篇博客写了一下排序二叉树，但是排序二叉树有一个退化问题：

假设我们向排序二叉树中依次插入 $[1, 2, 3, 5, 6, . . . ., N]$ 就会生成如下图的排序二叉树：

这就成为了一条单列表一样。
退化后的排序二叉树的时间复杂度为： $O (n)$
为了避免排序二叉树的退化我们产生了平衡二叉树。

平衡二叉树：

平衡二叉树的性质：

左子树和右子树深度之差的绝对值不大于1
左子树和右子树也都是平衡二叉树

平衡因子：

二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。
平衡二叉树上每个结点的平衡因子只可能是-1、0和1。

平衡化旋转：

在对平衡二叉树进行插入或删除一个结点后，通常会影响到从根结点到插入/删除结点的路径上的某些结点的平衡。这时就需要通过平衡化旋转的方法来将失衡的节点平衡化。
平衡化旋转有四个：LL型、LR型、RR型和RL型，其中主要的旋转只有两个：LL型和RR型；其他两种是通过这两种得到的；再说的明白点就是：LL型就是顺时针旋转，RR型就是逆时针旋转。
假设 $A$ 为失衡点，并且 $A$ 的所有子树都未失衡， $B$ 为 $A$ 的左儿子节点， $C$ 为 $A$ 的右儿子节点， $B_L$ 和 $B_R$ 分别是B的左右儿子， $C_L$ 和 $C_R$ 分别是 $C$ 的左右儿子。
LL型平衡化旋转
- 失衡条件： $A_{balance factor}=2$ $a n d$ $B_{balance factor}=1$ 。这种情况下是 $A$ 失衡是因为 $A$ 的左子树 $(L)$ 的左子树 $(L)$ 太长造成，这也是为啥叫LL旋转的原因。
- 平衡化旋转方法: 通过以 $A$ 为中心顺时针旋转操作实现:
RR型平衡化旋转
- 失衡原因： $A_{balance factor}=-2$ $a n d$ $C_{balance factor}=-1$ 这种情况下是 $A$ 失衡是因为 $A$ 的右子树 $(R)$ 的右子树 $(R)$ 太长造成。
- 平衡化旋转方法: 通过以 $A$ 为中心逆时针旋转操作实现：
LR型平衡化旋转
- 失衡原因： $A_{balance factor}=2$ $a n d$ $C_{balance factor}=-1$ 这种情况下是 $A$ 失衡是因为 $A$ 的右子树 $(L)$ 的右子树 $(R)$ 太长造成。
- 平衡化旋转方法: 先通过以 $B$ 为中心逆时针旋转操作；再通过以 $A$ 为中心顺时针旋转操作实现：
RL型平衡化旋转
- 失衡原因： $A_{balance factor}=-2$ $a n d$ $C_{balance factor}=1$ 这种情况下是 $A$ 失衡是因为 $A$ 的右子树 $(R)$ 的右子树 $(L)$ 太长造成。
- 平衡化旋转方法: 先通过以 $C$ 为中心顺时针旋转操作；再通过以 $A$ 为中心逆时针旋转操作实现：
特殊的平衡化旋转
- 失衡原因： $A_{balance factor}=-2$ $a n d$ $C_{balance factor}=0$ 和 $A_{balance factor}=2$ $a n d$ $B_{balance factor}=0$ 这种情是在删除的情况下出现的。
- 平衡化旋转方法:
  - 前一种情况：RR型和RL型旋转都可以将其转化为平衡状态，一般情况我们选择用RR型旋转，相对比较简单。
  - 后一种情况：LL型和LR型旋转都可以将其转化为平衡状态，一般情况我们选择用LL型旋转，相对比较简单。
总结
- 上面的一些思路理解本博客就没有详细的说明了，读者可以稍加思考应该就可以理解。但下面这个结论对后面插入和删除操作的理解非常重要：
- 若某一个节点因插入(删除)失衡，则该插入操作经过任何一个旋转操作的某个节点，其对应的子树的高度都变化1，可能增加1(插入)也可能减少1(删除)

插入操作：

原则：插入使得某个节点失衡，一定是因为插入使得该节点对应的子树高度增加1，而我们进行旋转使得该节点恢复平衡，这个旋转一定会使该节点对应的子树高度减少1，这样最后该节点对应的子树的高度保持不变，那么该节点的祖先节点都会保持不变。
步骤：
- 先使用排序二叉树的插入操作将节点X插入，并记下路径 $P a t h$ 。
- 选择路径中离插入点最近的插入前平衡因子不为0的点 $A$ 。
- $A$ 到 $X$ 的路径上除 $A$ 以外所有点 $(A, X]$ 的平衡因子都为0，即 $(A, X)$ 内的节点的左右子树的高度是一样的，那么插入 $X$ 后 $(A, X)$ 内的节点高度都会增加1,但都不失衡。
- $A$ 节点的平衡因子不为0，说明其左右子树高度不一致，而且 $X$ 肯定是插入到 $A$ 的左子树或右子树内的，并且插入 $X$ 的该子树的高度肯定怎加1.
- 如果插入 $X$ 的这个子树原来就比另一个子树高1，则以A为根的子树高度加1，并且 $A$ 失衡.这时我们对A进行相应的旋转，旋转后，以A为根的子树高度减1，这相当于以A为根的子树高度不变，则路径 $P a t h$ 中根到A的所有节点不会失衡。插入完成
- 如果插入 $X$ 的这个子树原来就比另一个子树低1，则以 $A$ 为根的子树高度不变，则路径 $P a t h$ 中根到 $A$ 的所有节点不会失衡。插入完成

删除操作：

原则：删除使得某个节点失衡，那么删除一定不会改变该节点对应的子树的高度(一定是使该节点较矮的左或右子树变的更矮)，而我们进行旋转使得该节点恢复平衡，这个旋转一定会使该节点对应的子树高度减少1，这样最后该节点对应的子树的高度会减少1，这样该节点的祖先节点也可能失去平衡。所有要继续向上查看是否还有失衡点。直到我们找到一个不失衡并且高度不变的节点，这个点的祖先节点一定不变。
步骤：
- 先按二叉排序树的查找方法查找到要删除的节点A。
- 再删除A节点：
  - 如果该节点在叶子节点我们直接令它为空
  - 如果该节点只有左或右子树，直接将其左或右子树提上来替换该节点。
  - 如果该节点有左右两个子树：
    - 若左子树高，就用左子树的最大值(最右边)，与当前节点交换，然后再向下递归删除节点。
    - 若右子树高，就用右子树的最小值(最左边)，与当前节点交换，然后再向下递归删除节点。
- 删除节点后下面的子树是保持不变的所有肯定不会失衡，可能失衡的点是在根到删除节点这条路径上的点[T,A)。
- 从删除点向上回溯，并不断更新路上节点的高度。若失衡我们就进行旋转调整，直到一个高度不变并且保持平衡的点结束，或者到根节点。

代码：

#include <iostream>
using namespace std;

struct Node
{
    int val;
    Node *Lchild;
    Node *Rchild;
    int height;
};

int Get_height(Node *T)
{
    int Len=-1;
    if(T->Rchild!=NULL &&T->Rchild->height>Len)
        Len=T->Rchild->height;
    if(T->Lchild!=NULL &&T->Lchild->height>Len)
        Len=T->Lchild->height;
    return Len+1;
}

int Get_Bfactor(Node *T)
{
    int Bfactor=0;
    if(T->Lchild!=NULL )
        Bfactor=T->Lchild->height+1;
    if(T->Rchild!=NULL )
        Bfactor=Bfactor-(T->Rchild->height+1);
    return Bfactor;
}

Node *LL_rotate(Node *T)
{
    Node *L =T->Lchild ;
    T->Lchild=L->Rchild ;
    L->Rchild=T ;
    //注意要更新结点的高度和平衡因子
    T->height = Get_height(T);
    L->height = Get_height(L);
    return L;
}

Node *RR_rotate(Node *T)
{
    Node *R=T->Rchild ;
    T->Rchild=R->Lchild ;
    R->Lchild=T ;
    //注意要更新结点的高度平衡因子
    T->height = Get_height(T);
    R->height = Get_height(R);
    return R;
}

Node *LR_rotate(Node *T)
{
    T->Lchild=RR_rotate(T->Lchild);
    T=LL_rotate(T);
    return T;
}

Node *RL_rotate(Node *T)
{
    T->Rchild=LL_rotate(T->Rchild);
    T=RR_rotate(T);
    return T;
}

//flag用于标志
Node *Insert_new(Node *T, int x,int &flag)
{
    if(T==NULL)//插入
    {
        flag=1;
        Node *S=new Node;
        S->Lchild=S->Rchild=NULL;
        S->val=x;
        S->height=0;
        return S;
    }
    int B_factor=Get_Bfactor(T);//当前节点没原来的平衡因子
    if(T->val==x)//已存在
        flag=0;
    else if(T->val>x)
        T->Lchild=Insert_new(T->Lchild, x,flag);
    else
        T->Rchild=Insert_new(T->Rchild, x,flag);

    if(flag==1)
    {
        T->height=Get_height(T);//更新树高
        if (B_factor!=0)//最近的可能失衡的点
            flag=2;
        if(flag==2)
        {
            if (Get_Bfactor(T)==2)//左子树失衡
            {
                if (Get_Bfactor(T->Lchild)==1)
                    T=LL_rotate(T) ;
                else
                    T=LR_rotate(T) ;
            }
            if (Get_Bfactor(T)==-2)//右子树失衡
            {
                if (Get_Bfactor(T->Rchild)==-1)
                    T=RR_rotate(T);
                else
                    T=RL_rotate(T);
            }
        }
    }
    return T;
}

//flag用于标志
Node *Delete(Node *T, int key,bool &flag)
{
    //没有找到该结点
    if (T==NULL)
    {
        flag=false;
        return NULL;
    }

    //找到结点,将它删除
    if (key == T->val)
    {
        flag=true;
        //待删除节点为叶子结点。
        if (T->Lchild==NULL && T->Rchild==NULL)
            return NULL;
        //待删除结点只有右孩子。
        else if (T->Lchild==NULL)
            return T->Rchild;
        //待删除结点只有左孩子。
        else if (T->Rchild==NULL)
            return T->Lchild;
        //待删除结点既有左孩子，又有右孩子
        else
        {
            if (T->Lchild->height > T->Rchild->height)
            {
                //寻找前驱结点pre
                Node *pre = T->Lchild;
                while (pre->Rchild)//一直往右寻找最大值
                    pre = pre->Rchild;
                //用pre替换T。
                T->val = pre->val;
                //删除节点pre。
                T->Lchild=Delete(T->Lchild, pre->val,flag);
            }
            else
            {
                //寻找后继节点post
                Node *post = T->Rchild;
                while (post->Lchild)//一直往左寻找最小值
                    post = post->Lchild;
                //用post替换*T
                T->val = post->val;
                //删除节点post
                T->Rchild=Delete(T->Rchild, post->val,flag);
            }
        }
    }

    //在左子树中递归删除
    if (key < T->val)
        T->Lchild=Delete(T->Lchild, key,flag);
    else
        T->Rchild=Delete(T->Rchild, key,flag);

    //删除成功，更新路径上的点
    if(flag)
    {
        //修改树的高度和平衡因子
        T->height=Get_height(T);
        if (Get_Bfactor(T)==-2)//R
        {
            //T->Rchild->Bfactor==0时可以RR也可以RL;但是RR相对简单
            if (Get_Bfactor(T->Rchild)==1)//L
                T=RL_rotate(T);
            else//R
                T=RR_rotate(T);
        }
        if (Get_Bfactor(T)==2)//L
        {
            //T->Lchild->Bfactor==0时可以LL也可以LR
            if (Get_Bfactor(T->Lchild)==-1)//R
                T=LR_rotate(T);
            else//L
                T=LL_rotate(T);
        }
    }
    return T;
}


void DFS(Node *p)
{
    if(p!=NULL)
    {
        cout<<p->val<<" "<<p->height<<" "<<Get_Bfactor(p)<<endl;
        DFS(p->Lchild);
        DFS(p->Rchild);
    }
}

int main()
{
    int flag;
    bool flag1;
    Node *Root=NULL;
    Node *Root_new=NULL;
    int n;
    int data[100];
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>data[i];
    cout<<"==========================="<<endl;
    for(int i=0; i<n; i++)
    {
        flag=0;
        Root_new=Insert_new(Root_new,data[i],flag);
    }
    DFS(Root_new);
    cout<<"++++++++++++++++++++++++++++++"<<endl;
    flag1=false;
    Root_new=Delete(Root_new,70,flag1);
    DFS(Root_new);
    cout<<"==========================="<<endl;
    flag1=false;
    Root_new=Delete(Root_new,9,flag1);
    DFS(Root_new);
    cout<<"==========================="<<endl;
}

/*
9
50 20 10 60 70 30 9 12 15
*/