AVL树

谁借莪１个温暖的怀抱￠ 2022-01-15 01:39 204阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

平衡二叉树，是一个方便查找的树，树的左子树深度与右子树的深度的差总（BF）是在+1,0,-1之中。

随着树的建立，插入，树都会自动的进行调整，使得其满足上面的条件。

**1、+1表示左子树的深度比右子树的深度多1.**

**2、0 表示左子树的深度与右子树的深度相同。**

**3、-1表示左子树的深度比右子树神的小1.**

因此，如果一个数据插入到情况1中，也就是说，数据插入到左子树中，左子树的深度将会比右子树多2.此时，需要调整树的结构。如果插入尾端节点的左子树中，则这个尾端节点相应的BF值,就变成+1.相反，如果插入到它的右子树中，BF值就会变成-1.这个调整也会返回到上面一层的节点，再次进行调整。

这里相应的介绍一个左旋，与右旋的基本知识。

比如下图

![15165438_TAK2.png][]

在进行左旋时，将会发生下面的情况：

void L_Rotate(BiTree *p){
        //传入根节点进行右旋
        BiTree R;
        R = (*p)->rchild;
        (*p)->rchild = R->lchild;
        R->lchild = (*p);
        (*p) = R;
    }

最后子树将会变成

![15165439_VpnU.png][]

相应的右旋，则运行下面的代码

void R_Rotate(BiTree *p){
        //传入一个根节点，进行右旋。定义它的左子树节点为L,根节点的左子树变成L的右子树，L的右子树变成根节点。最后把根节点指针指向L
        BiTree L;
        L = (*p)->lchild;
        (*p)->lchild =  L->rchild;
        L->rchild = (*p);
        (*p) = L;
    }

了解左旋与右旋后，就该进行树的调整介绍了。

这里有一个技巧：

1 如果插入的元素插入到左子树，使得左子树的BF值发生改变。**如果左子树节点的BF值，与根节点的BF值相同符号**，则进行一次右旋，即可。但是如果是不同符号，则要进行双旋（即先进性左旋，使得子树高度加一，在进行右旋，平衡子树）

2 如果插入到右子树，也观察符号，相同，则进行一次右旋，如果不同，则进行双旋。

代码如下

void LeftBalance(BiTree *T){
        BiTree L,Lr;
        L = (*T)->lchild;
        switch(L->bf){
        case LH://符号与根相同，因此进行右旋一次，就行了
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH://符号与根不同，要进行双旋；对子树进行一次旋转，再对T进行一次旋转
            Lr = L->rchild;
            switch(Lr->bf){
            case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
                (*T)->bf = RH;
                L->bf = EH;
                break;
            case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
                (*T)->bf = L->bf = EH;
                break;
            case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
                (*T)->bf = EH;
                L->bf = LH;
                break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
        }
    }
    
    void RightBalance(BiTree *T){
        BiTree R,Rl;
        R = (*T)->rchild;
        switch(R->bf){
        case RH:
            (*T)->bf = R->bf = EH;
            L_Rotate(T);
            break;
        case LH:
            Rl = R->lchild;
            switch(Rl->bf){
            case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
                (*T)->bf = EH;
                R->bf = RH;
                break;
            case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
                (*T)->bf = R->bf = EH;
                break;
            case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
                (*T)->bf = LH;
                R->bf = EH;
                break;
            }
            Rl->bf = EH;
            R_Rotate(&(*T)->rchild);
            L_Rotate(T);
        }
    }

插入时，要遍历到子树的最底层，进行分析，逐层的改变BF值，进行平衡。知道标记taller为0时，表示对深度不发生改变，就不需要向上遍历了。

int insertAVL(BiTree *T,int e, int *taller){
        if(!(*T)){
            (*T)=(BiTree)malloc(sizeof(BiTNode));
            (*T)->data = e;
            (*T)->lchild = NULL;
            (*T)->rchild = NULL;
            (*T)->bf = EH;
            *taller = 1;
        }else{
            if(e == (*T)->data){ //存在相同节点
                *taller = 0;
                return 0;
            }
            if(e < (*T)->data){
                if(!insertAVL(&(*T)->lchild,e,taller))
                    return 0;
                if(taller){
                    switch((*T)->bf){
                    case LH:
                        LeftBalance(T);
                        *taller = 0;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = 1;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = 0;
                        break;
                    }
                }
            }else{
                if(!insertAVL(&(*T)->rchild,e,taller))
                    return 0;
                if(taller){
                    switch((*T)->bf){
                    case LH:
                        (*T)->bf = 0;
                        *taller = 0;
                        break;
                    case EH:
                        (*T)->bf=RH;
                        *taller = 1;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = 0;
                        break;
                    }
                }
            }
        }
        return 1;
    }

## 全部代码： ##

![15165439_WG4P.gif][] ![15165439_Rjsi.gif][]

#include <stdio.h>
    #include <stdlib.h>
    #define LH +1
    #define EH 0
    #define RH -1
    
    typedef struct BiTNode{
        int data;
        int bf;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    void R_Rotate(BiTree *p);
    void L_Rotate(BiTree *p);
    void LeftBalance(BiTree *p);
    void RightBalance(BiTree *T);
    int insertAVL(BiTree *T,int e, int *taller);
    void InOrderTree(BiTree b);
    
    int main(){
        int i;
        int a[10]={
          4,7,9,1,2,3,0,5,6,8};
        BiTree T = NULL;
        int *taller = (int *)malloc(sizeof(int));
        for(i=0;i<10;i++){
            insertAVL(&T,a[i],taller);
            InOrderTree(T);
            printf("\n");
        }
        getchar();
    }
    void InOrderTree(BiTree b){
        if( b== NULL)
            return;
        InOrderTree(b->lchild);
        printf("%d ",b->data);
        InOrderTree(b->rchild);
    }
    int insertAVL(BiTree *T,int e, int *taller){
        if(!(*T)){
            (*T)=(BiTree)malloc(sizeof(BiTNode));
            (*T)->data = e;
            (*T)->lchild = NULL;
            (*T)->rchild = NULL;
            (*T)->bf = EH;
            *taller = 1;
        }else{
            if(e == (*T)->data){ //存在相同节点
                *taller = 0;
                return 0;
            }
            if(e < (*T)->data){
                if(!insertAVL(&(*T)->lchild,e,taller))
                    return 0;
                if(taller){
                    switch((*T)->bf){
                    case LH:
                        LeftBalance(T);
                        *taller = 0;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = 1;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = 0;
                        break;
                    }
                }
            }else{
                if(!insertAVL(&(*T)->rchild,e,taller))
                    return 0;
                if(taller){
                    switch((*T)->bf){
                    case LH:
                        (*T)->bf = 0;
                        *taller = 0;
                        break;
                    case EH:
                        (*T)->bf=RH;
                        *taller = 1;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = 0;
                        break;
                    }
                }
            }
        }
        return 1;
    }
    
    void R_Rotate(BiTree *p){
        //传入一个根节点，进行右旋。定义它的左子树节点为L,根节点的左子树变成L的右子树，L的右子树变成根节点。最后把根节点指针指向L
        BiTree L;
        L = (*p)->lchild;
        (*p)->lchild =  L->rchild;
        L->rchild = (*p);
        (*p) = L;
    }
    void L_Rotate(BiTree *p){
        //传入根节点进行右旋
        BiTree R;
        R = (*p)->rchild;
        (*p)->rchild = R->lchild;
        R->lchild = (*p);
        (*p) = R;
    }
    void LeftBalance(BiTree *T){
        BiTree L,Lr;
        L = (*T)->lchild;
        switch(L->bf){
        case LH://符号与根相同，因此进行右旋一次，就行了
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH://符号与根不同，要进行双旋；对子树进行一次旋转，再对T进行一次旋转
            Lr = L->rchild;
            switch(Lr->bf){
            case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
                (*T)->bf = RH;
                L->bf = EH;
                break;
            case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
                (*T)->bf = L->bf = EH;
                break;
            case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
                (*T)->bf = EH;
                L->bf = LH;
                break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
        }
    }
    
    void RightBalance(BiTree *T){
        BiTree R,Rl;
        R = (*T)->rchild;
        switch(R->bf){
        case RH:
            (*T)->bf = R->bf = EH;
            L_Rotate(T);
            break;
        case LH:
            Rl = R->lchild;
            switch(Rl->bf){
            case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
                (*T)->bf = EH;
                R->bf = RH;
                break;
            case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
                (*T)->bf = R->bf = EH;
                break;
            case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
                (*T)->bf = LH;
                R->bf = EH;
                break;
            }
            Rl->bf = EH;
            R_Rotate(&(*T)->rchild);
            L_Rotate(T);
        }
    }

## 运行实例： ##

![15165439_MBRA.png][]

转载于:https://my.oschina.net/u/204616/blog/545300

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/5925645c0ead4588aeac06f06ea53922.png
[15165438_TAK2.png]: /images/20220114/19f76c2c511f437f8866073188b64c31.png
[15165439_VpnU.png]: /images/20220114/dd395489e1fa4079be8337acea417ab6.png
[15165439_WG4P.gif]: http://static.oschina.net/uploads/img/201512/15165439_WG4P.gif
[15165439_Rjsi.gif]: /images/20220114/a48ea028e9444e3d9b34983c71e47d6a.png
[15165439_MBRA.png]: /images/20220114/b52bf7e508fd465cb7879c4e5ce52f2d.png