美文网首页
平衡二叉树(AVL树)

平衡二叉树(AVL树)

作者: lxr_ | 来源:发表于2022-08-21 21:05 被阅读0次

    1.平衡二叉树(Self-Balancing Binary Search Tree 或者 Height-Balanced Binary Search Tree)是一种二叉排序树,其中每个结点的左子树和右子树的高度差之多等于1。
    2.将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor),只可能是-1,0,1。
    如下图左图中58结点的平衡因子为3,故不是平衡二叉树,经过调整后右图为平衡二叉树。


    3.距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,称为最小不平衡子树,平衡二叉树的思想就是将不平衡消灭在最早时刻
    如下图中,插入结点37后,58,62结点的平衡因子都为2,但是以58为根结点的子树距离37结点最近,故该子树为最小不平衡子树。
    最小不平衡子树
    4.失衡二叉排序树的分析与调整:
    平衡调整分为四种类型:LL型、LR型、RL型、RR型,通过调整原则:降低高度、保持二叉排序树的性质,当出现失衡二叉排序树时,其调整结果如下。
    失衡二叉树的调整
    当然,这些结点上还可能有其他结点,具体来说如下图所示:
    LL型调整
    RR型调整
    LR型调整
    RL型调整
    注:实际情况不止图示的一种,新插入的结点可能位于某个结点的左孩子或者右孩子,都有可能
    代码示例
    AVL.h
    #pragma once
    
    #include <iostream>
    
    using namespace std;
    
    #define LH +1       //左高
    #define EH 0        //等高
    #define RH -1       //右高
    
    typedef struct BiTNode          //平衡二叉树结点结构
    {
        int data;                   //结点数据
        int bf;                     //结点的平衡因子
        BiTNode* lchild, * rchild;  //左右孩子指针
    }*BiTree;
    
    //右旋操作,顺时针
    void R_Rotate(BiTNode*& p);     //因为要修改指针,故需要传递二级指针(此处采用引用的方式)
    
    //右旋操作,逆时针
    void L_Rotate(BiTNode*& p);
    
    //左平衡旋转(针对LL或者LR型)
    void LeftBalance(BiTNode*& p);
    
    //右平衡旋转(针对RR或者RL型)
    void RightBalance(BiTNode*& p);
    
    //插入平衡二叉树
    bool InsertAVL(BiTree& T, int e, bool* taller);
    
    //中序遍历
    void InOrderTraverse(BiTree T);
    

    AVL.cpp

    #include "AVL.h"
    
    //右旋操作,顺时针
    void R_Rotate(BiTNode*& p)
    {
        BiTNode* l = p->lchild;         //p的左孩子
        p->lchild = l->rchild;          //p的左孩子为左孩子的右孩子
        l->rchild = p;                  //p的左孩子的右孩子为p
    
        p = l;                          //p结点指向新的根结点
    
    }
    //右旋操作,逆时针
    void L_Rotate(BiTNode*& p)
    {
        BiTNode* r = p->rchild;         //p结点的右孩子
        p->rchild = r->lchild;
        r->lchild = p;
    
        p = r;
    }
    
    //左平衡旋转(针对LL或者LR型)此时已经插入结点完成,需要进行平衡调整
    void LeftBalance(BiTNode*& p)
    {
        BiTNode* l, * lr;
        l = p->lchild;                  //p结点的左孩子
    
        switch (l->bf)                  //检查左孩子的平衡度
        {
        case LH:                        //如果为左高,则为LL型
            p->bf = l->bf = EH;         //调整后p和l的平衡度为0
            R_Rotate(p);                //右旋
            break;
    
        case RH:                        //如果为右高,则为LR型
            lr = l->rchild;             //p结点左孩子的右孩子
            //1.修改bf
            switch (lr->bf)
            {
            case LH:                    //如果左高,说明添加在了lr的左子树上
                p->bf = RH;
                l->bf = EH;
                break;
            case EH:                    //如果为等高
                p->bf = l->bf = EH;
                break;
            case RH:                    //如果为右高,则添加在了lr的右子树上
                p->bf = EH;
                l->bf = LH;
                break;
            default:
                break;
            }
            //2.旋转
            lr->bf = EH;
            L_Rotate(p->lchild);        //先左旋
            R_Rotate(p);                //后右旋
    
        default:
            break;
        }
    }
    
    //右平衡旋转(针对RR或者RL型)
    void RightBalance(BiTNode*& p)
    {
        BiTNode* r, * rl;
        r = p->rchild;
        switch (r->bf)
        {
    
        case RH:                        //如果为右高,则为RR型
            p->bf = r->bf = EH;
            L_Rotate(p);
            break;
        case LH:                        //如果为左高,则为RL型
            rl = r->lchild;             //p结点右孩子r的左孩子rl
            //1.修改bf
            switch (rl->bf)
            {
            case LH:
                p->bf = EH;
                r->bf = RH;
                break;
            case EH:
                p->bf = r->bf = EH;
                break;
            case RH:
                p->bf = LH;
                r->bf = EH;
                break;
    
            default:
                break;
            }
            //2.旋转
            rl->bf = EH;
            R_Rotate(p->rchild);        //先右旋
            L_Rotate(p);                //后左旋
            break;
        default:
            break;
        }
    }
    
    //插入平衡二叉树
    bool InsertAVL(BiTree& T, int e, bool* taller)
    {
    
        if (!T)                         //找到了插入位置
        {
            T = new BiTNode;
            T->data = e;
            T->lchild = T->rchild = NULL;
            T->bf = EH;
            *taller = true;             //插入成功后,默认树长高
        }
        else
        {
            if (e == T->data)           //树中已经存在和e有相同关键字的结点,则不再插入
            {
                *taller = false;
                return false;
            }
    
            if (e < T->data)            //如果插入值比根结点小,则在左子树中继续寻找
            {
                if (!InsertAVL(T->lchild, e, taller))
                {
                    return false;       //未插入成功
                }
    
                if (*taller)            //如果插入成功,且左子树长高
                {
                    switch (T->bf)      //检查T的平衡度
                    {
                    case LH:            //原本左子树比右子树高,需要左平衡处理
                        LeftBalance(T);
                        *taller = false;
                        break;
                    case EH:            //原本左右子树等高,现在因左子树增高而树增高
                        T->bf = LH;
                        *taller = true;
                        break;
                    case RH:
                        T->bf = EH;     //原本右子树比左子树高,现左右子树等高
                        *taller = false;
    
                    default:
                        break;
                    }
                }
            }
            else                        //否则在右子树中寻找插入位置
            {
                if (!InsertAVL(T->rchild, e, taller))
                {
                    return false;       //未插入成功
                }
    
                if (*taller)            //如果插入成功,且右子树长高
                {
                    switch (T->bf)
                    {
                    case LH:            //原本左子树比右子树高,现在左右子树等高
                        T->bf = EH;
                        *taller = false;
                        break;
                    case EH:            //原本左右子树等高,现在因右子树增高而树叶增高
                        T->bf = RH;
                        *taller = true; //树长高后,用于判断下一个以父结点为根结点的子树是否失衡
                        break;
                    case RH:            //失衡
                        RightBalance(T);
                        *taller = false;//调整之后树不会长高,故不需要判断下一个以父结点为根结点的子树是否失衡
                        break;
    
                    default:
                        break;
                    }
                }
            }
    
        }
    
        return true;
    }
    
    //中序遍历
    void InOrderTraverse(BiTree T)
    {
        if (T == NULL)
        {
            return;
        }
        InOrderTraverse(T->lchild);
        cout << T->data << " ";
        InOrderTraverse(T->rchild);
    }
    

    main.cpp

    #include "AVL.h"
    
    #include <iostream>
    
    using namespace std;
    
    void test(int* p)
    {
        cout << "test:&p=" << &p << endl;
    }
    int main(int argc, char** argv)
    {
        int a[10] = { 3,2,1,4,5,6,7,10,9,8 };
        BiTree T = NULL;
        bool taller;
        for (int i = 0; i < 10; i++)
        {
            InsertAVL(T, a[i], &taller);
        }
    
        InOrderTraverse(T);
    
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:平衡二叉树(AVL树)

          本文链接:https://www.haomeiwen.com/subject/wpxwgrtx.html