AVL树的基本概念

AVL树的定义

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis。

AVL树本质上是一颗二叉搜索树，并且本身带有平衡的条件，即每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

AVL树可以始终将其高度控制在 ，从而保证AVL树的平衡。

平衡因子

平衡因子（balance factor）指的是一个节点的左右子树的高度差。在AVL树中，任意一个节点的平衡因子绝对值不会超过 1 。

一般情况下，我们将单个节点的高度初始化为1，所以空树高度即为0，而树中叶子节点的高度就为1。在进行节点插入操作后，也将对树的高度进行调整。左右子树的高度是判断当前树是否满足AVL树的标准，所以，在AVL树的节点结构体中，我们还需要加入高度参数 height，同时也需要相对于的取高度函数，这样更加方便。

typedef struct BiNode{

    int val;
    int height;        //需记录每个节点的高度
    struct BiNode *left, *right;

}BiNode, *BinaryTree;

//返回节点的高度
int GetHeight(BinaryTree root){
    return root ? root->height : 0;
}

失衡与重平衡

在AVL树中插入和删除的操作是根据二叉搜索树的性质来实现的，这样的话可能会导致二叉树高度的变化，从而可能导致节点的左右子树高度差的绝对值大于1，使得不再满足AVL树的性质。我们需要找到最小不平衡子树，然后进行旋转调整，使之再次满足AVL树的性质。

AVL树的旋转方式主要分为单旋和双旋，其中单旋分为 LL型 和 RR型，双旋 分为 LR型 和 RL型 。

在进行完旋转操作之后，还需要对当前最小不平衡子树的根节点的高度进行调整。

AVL树的插入操作时的调整

LL型 右旋

LL型旋转

LL型指的是，新插入的节点位于最小不平衡子树的左子树的左子树上的情况，此时因为左子树过高而导致不平衡。此时需要进行右旋，使得子树平衡。

最小不平衡子树的根节点为 root，我们需要将其左儿子作为新的根节点 newroot，并将 root 变成 newroot 的右子树根节点。观感上就是顺时针旋转或者向右旋转，这样可以使得最小不平衡子树的左子树的高度减小，右子树的高度增加，从而达到平衡。

但是，如果说左子树存在右子树，那么在将 root 变成 newroot 的右子树根节点之前，需要将这个右子树先继承给 root ，变成其左子树。这样一定是合法的，因为当前 newroot 后来会变成新的根节点，不再作为 root 的左子树，而且 newroot 的右子树所有节点值满足小于 root 的节点值。故我们可以把 newroot->right 先变成 root->left，再将 root 变成 newroot->right。

大致步骤为：
（1）Node newroot = root->left
（2）root->left = newroot->right*
（3）newroot->right = root
（4）调整 root，newroot 高度

调整高度只需要更新成取节点左右子树中较大的高度，然后再 +1 就可以了，节点的左右子树高度本质上是没有改变的（此时暂且忽略新插入的节点）。

LL型旋转 图解

动画演示

逐帧图解

（1）

（2）

（3）

（4）

（5）

（6）

LL型旋转 代码

//插入节点位于最小不平衡子树根节点的左儿子的左子树上  LL 进行右旋
BinaryTree LL_rotate(BinaryTree &root){
    BinaryTree newroot = root->left;     //右旋，左儿子成为新的根节点
    root->left = newroot->right;         //左儿子的右子树成为根节点的左子树
    newroot->right = root;               //之前根节点成为新根节点的右子树

    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    newroot->height = std::max(GetHeight(newroot->left), GetHeight(newroot->right)) + 1;

    return newroot;
}

RR型 左旋

RR型旋转

RR型指的是，新插入的节点位于最小不平衡子树的右子树的右子树上的情况，此时因为右子树过高而导致不平衡。此时需要进行左旋，使得子树平衡。

最小不平衡子树的根节点为 root，我们需要将其右儿子作为新的根节点 newroot，并将 root 变成 newroot 的左子树根节点。观感上就是逆时针旋转或者向左旋转，这样可以使得最小不平衡子树的右子树的高度减小，左子树的高度增加，从而达到平衡。

与LL型类似地，如果说右子树有左子树，那么在将 root 变成 newroot 的左子树根节点之前，需要将右子树的左子树先继承给 root ，变成其右子树。当前 newroot 后来会变成新的根节点，不再作为 root 的右子树，而且 newroot 的左子树所有节点值满足大于于 root 的节点值。故我们可以把 newroot->left 先变成 root->right，再将 root 变成 newroot->left。

大致步骤为：
（1）Node newroot = root->right
（2）root->right = newroot->left*
（3）newroot->left = root
（4）调整 root，newroot 高度

RR型旋转 图解

动画演示

逐帧图解

（1）

（2）

（3）

（4）

（5）

（6）

RR型旋转 代码

//插入节点位于最小不平衡子树根节点的右儿子的右子树上  RR  进行左旋
BinaryTree RR_rotate(BinaryTree &root){
    BinaryTree newroot = root->right;    //左旋，右儿子变成新的根节点
    root->right = newroot->left;         //右儿子的左子树变成当前根节点的右子树
    newroot->left = root;                //原先根节点变成新根节点的左子树

    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    newroot->height = std::max(GetHeight(newroot->left), GetHeight(newroot->right)) + 1;

    return newroot;
}

LR型 先左旋再右旋

LR型旋转

LR型指的是，插入的新节点位于最小不平衡子树根节点 root 的左子树的右子树上，由于左子树过高而导致不平衡。此时我们要先对左子树进行RR型左旋，将整棵树变成LL型的局面，然后对整棵树进行LL右旋。

这类情况看起来要稍微复杂一点，不过之前我们已经实现了LL型和RR型的旋转函数，所以只要建立在这个基础上来实现LR型旋转函数就可以了。

大致步骤为：
（1）root->left = RRrotate(root->left)
（2）return LLrotate(root)

（在RRrotate和LLrotate中已经将高度调整完成了）

LR型旋转 图解

动画演示

逐帧图解

（1）

（2）

（3）

（4）

（5）

（6）

LR型旋转 代码

//插入节点位于最小不平衡子树根节点root的左儿子的右子树上 LR  先左旋左儿子，再右旋根节点
BinaryTree LR_rotate(BinaryTree &root){
    root->left = RR_rotate(root->left);  //左旋左儿子
    return LL_rotate(root);              //右旋根节点
}

RL型 先右旋再左旋

RL型旋转

RL型指的是，插入的新节点位于最小不平衡子树根节点 root 的右子树的左子树上，由于右子树过高而导致不平衡。此时我们要先对右子树进行LL型右旋，将整棵树变成RR型的局面，然后对整棵树进行RR左旋。

与LR型相类似，只要建立在LL型和RR型的旋转函数的基础上实现就可以。

大致步骤为：
（1）root->right = LLrotate(root->right)
（2）return RRrotate(root)

（在LLrotate和RRrotate中已经将高度调整完成了）

RL型旋转 图解

动画演示

逐帧图解

（1）

（2）

（3）

（4）

（5）

（6）

RL型旋转 代码

//插入节点位于最小不平衡子树根节点root的右儿子的左子树上 RL  先右旋右儿子，再左旋根节点
BinaryTree RL_rotate(BinaryTree &root){
    root->right = LL_rotate(root->right);//右旋右儿子
    return RR_rotate(root);              //左旋根节点
}

AVL树插入时旋转方式的判断

插入后左子树更高且高度差大于1

（1）插入节点值比左子树根节点值小：此时插入节点位于左子树的左子树上，为 LL型

（2）插入节点值比左子树根节点值大：此时插入节点位于左子树的右子树上，为 LR型

插入后右子树更高且高度差大于1

（1）插入节点值比右子树根节点值大：此时插入节点位于右子树的右子树上，为 RR型

（2）插入节点值比右子树根节点值小：此时插入节点位于右子树的左子树上，为 RL型

AVL树插入操作代码

//AVL树的插入
void Insert_AVL(BinaryTree &root, int val){
    BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
    node->val = val;
    node->left = node->right = NULL;
    node->height = 1;      //高度初始为1
    if(!root){
        root = node;
        return;
    }

    if(root->val == val)
        return;                      //已经存在这个值的节点 则不插入

    //递归插入AVL树
    if(root->val > val){                 //向左子树插入，有可能会使左子树变高
        Insert_AVL(root->left, val);
        //插入之后不平衡的调整
        if(GetHeight(root->left) - GetHeight(root->right) > 1){
            if(root->left->val > val){
                root = LL_rotate(root);  //如果插入位置为左儿子的左子树LL，右旋
            }else{
                root = LR_rotate(root);  //如果插入位置为左儿子的右子树LR，先左旋再右旋
            }
        }
    }else{                               //向右子树插入 有可能会使右子树变高
        Insert_AVL(root->right, val);
        //插入后不平衡的调整
        if(GetHeight(root->right) - GetHeight(root->left) > 1){
            if(root->right->val height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
}

AVL树的删除操作时的调整

AVL树删除操作部分和二叉搜索树是一样的，其中删除节点存在左右子树这一块比较复杂，如果有困惑的可以看我之前的一篇有关二叉搜索树的博客：
[数据结构] 二叉搜索树 (二叉排序树)

AVL树删除时旋转方式的判断

删除后左子树更高且高度差大于1

（1）左子树的左子树比左子树的右子树高：删除后形成了 LL型 的局面

（2）左子树的右子树比左子树的左子树高：删除后形成了 LR型 的局面

删除后右子树更高且高度差大于1

（1）右子树的右子树比右子树的左子树高：删除后形成了 RR型 的局面

（2）右子树的左子树比右子树的右子树高：删除后形成了 RL型 的局面

AVL树删除操作代码

//AVL删除节点
BinaryTree Delete_AVL(BinaryTree &root, int val){
    BinaryTree t = root, parent = NULL, s = NULL;
    if(!t){
        puts("要删除的节点不存在");
        return root;
    }

    /*          删除操作              */
    if(t->val > val){
        root->left = Delete_AVL(root->left, val);    //对左子树进行删除节点
    }else if(t->val right = Delete_AVL(root->right, val);  //对右子树进行删除节点
    }else{
        //当前root为删除的节点
        //判断此子树的性质
        if(!t->left && !t->right){       //**如果此子树没有儿子 
            root = NULL;                 //  直接删除即可
        }else if(!t->left && t->right){  //**如果没有左儿子 但是有右儿子  
            root = t->right;             //  将其右儿子代替当前删除的节点即可
        }else if(t->left && !t->right){  //**如果有左儿子 但是没有右儿子  
            root = t->left;              //  将其左儿子代替当前删除的节点即可
        }else{                           //**如果既有右儿子又有左儿子  就比较麻烦了
            s = t->right;             //  记录删除节点的右子树根节点
            if(!s->left){
                s->left = t->left;     //如果删除节点的右子树没有左儿子 只要将删除节点的左子树继承给s即可
            }else{
                //需找到删除节点右子树中最左边的节点 即第一个大于删除节点值的节点
                while(s->left){
                    parent = s;          //记录s的父节点
                    s = s->left;
                }

                parent->left = s->right; //若第一个大于删除节点的节点有右子树 继承给其父节点作为其左子树
                s->left = t->left;       //代替删除节点 继承其左子树
                s->right = t->right;     //代替删除节点 继承其右子树
            }

            root = s;                    //更新子树根
        }

        free(t);
    }

    /*         平衡操作              */
    if(!root)
        return NULL;                     //上面递归完之后若根节点都被删了

    //删除操作后可能需要调整高度
    if(GetHeight(root->left) - GetHeight(root->right) > 1){
        //左子树比右子树高 说明删除了右子树中的节点 
        //变向地认为在左子树中插入了节点 需要进行右旋
        if(GetHeight(root->left->left) > GetHeight(root->left->right)){
            return LL_rotate(root);      //左子树的左边更高  需要进行 LL 的右旋
        }else{
            return LR_rotate(root);      //左子树的右边高   需要进行  LR  的右旋
        }
    }else if(GetHeight(root->right) - GetHeight(root->left) > 1){
        //右子树比左子树更高  说明删除的是左子树中的节点
        //变向地认为在右子树插入了节点 需要进行左旋
        if(GetHeight(root->right->right) > GetHeight(root->right->left)){            
            return RR_rotate(root);      //右子树的右边更高 需要进行  RR  的左旋
        }else{
            return RL_rotate(root);      //右子树的左边更高 需要进行  RL  的左旋
        }
    }

    //更新root的高度
    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    return root;
}

程序测试

完整程序代码

#include
#include
#include
#include
#include
#include
//AVL树  Adelson-Velskii Landis

typedef struct BiNode{

    int val;
    int height;        //需记录每个节点的高度
    struct BiNode *left, *right;

}BiNode, *BinaryTree;

//判断是否存在target值节点
BinaryTree Search_AVL(BinaryTree root, int target){
    if(!root) return NULL;
    if(target == root->val) return root;
    if(target > root->val)
        return Search_AVL(root->left, target);
    else
        return Search_AVL(root->right, target);
}

//返回节点的高度
int GetHeight(BinaryTree root){
    return root ? root->height : 0;
}

//插入节点位于最小不平衡子树根节点的左儿子的左子树上  LL 进行右旋
BinaryTree LL_rotate(BinaryTree &root){
    BinaryTree newroot = root->left;     //右旋，左儿子成为新的根节点
    root->left = newroot->right;         //左儿子的右子树成为根节点的左子树
    newroot->right = root;                //之前根节点成为新根节点的右子树

    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    newroot->height = std::max(GetHeight(newroot->left), GetHeight(newroot->right)) + 1;

        return newroot;
}

//插入节点位于最小不平衡子树根节点的右儿子的右子树上  RR  进行左旋
BinaryTree RR_rotate(BinaryTree &root){
    BinaryTree newroot = root->right;    //左旋，右儿子变成新的根节点
    root->right = newroot->left;         //右儿子的左子树变成当前根节点的右子树
    newroot->left = root;                 //原先根节点变成新根节点的左子树

    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    newroot->height = std::max(GetHeight(newroot->left), GetHeight(newroot->right)) + 1;

        return newroot;
}

//插入节点位于最小不平衡子树根节点root的左儿子的右子树上 LR  先左旋左儿子，再右旋根节点
BinaryTree LR_rotate(BinaryTree &root){
    root->left = RR_rotate(root->left);  //左旋左儿子
    return LL_rotate(root);              //右旋根节点
}

//插入节点位于最小不平衡子树根节点root的右儿子的左子树上 RL  先右旋右儿子，再左旋根节点
BinaryTree RL_rotate(BinaryTree &root){
    root->right = LL_rotate(root->right);//右旋右儿子
    return RR_rotate(root);              //左旋根节点
}

//AVL树的插入
void Insert_AVL(BinaryTree &root, int val){
    BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
    node->val = val;
    node->left = node->right = NULL;
    node->height = 1;
    if(!root){
        root = node;
        return;
    }

    if(root->val == val)
        return;                      //已经存在这个值的节点 则不插入

    //递归插入AVL树
    if(root->val > val){                 //向左子树插入，有可能会使左子树变高
        Insert_AVL(root->left, val);
        //插入之后不平衡的调整
        if(GetHeight(root->left) - GetHeight(root->right) > 1){
            if(root->left->val > val){
                root = LL_rotate(root);  //如果插入位置为左儿子的左子树LL，右旋
            }else{
                root = LR_rotate(root);  //如果插入位置为左儿子的右子树LR，先左旋再右旋
            }
        }
    }else{                               //向右子树插入 有可能会使右子树变高
        Insert_AVL(root->right, val);
        //插入后不平衡的调整
        if(GetHeight(root->right) - GetHeight(root->left) > 1){
            if(root->right->val height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
}

//构建AVL树
void Create_AVL(BinaryTree &root, std::vector &v){
    for(auto x : v) Insert_AVL(root, x);
}

//AVL删除节点
BinaryTree Delete_AVL(BinaryTree &root, int val){
    BinaryTree t = root, parent = NULL, s = NULL;
    if(!t){
        puts("要删除的节点不存在");
        return root;
    }

    /*               删除操作              */
    if(t->val > val){
        root->left = Delete_AVL(root->left, val);    //对左子树进行删除节点
    }else if(t->val right = Delete_AVL(root->right, val);  //对右子树进行删除节点
    }else{
        //当前root为删除的节点
        //判断此子树的性质
        if(!t->left && !t->right){       //**如果此子树没有儿子 
            root = NULL;                 //  直接删除即可
        }else if(!t->left && t->right){  //**如果没有左儿子 但是有右儿子  
            root = t->right;             //  将其右儿子代替当前删除的节点即可
        }else if(t->left && !t->right){  //**如果有左儿子 但是没有右儿子  
            root = t->left;              //  将其左儿子代替当前删除的节点即可
        }else{                           //**如果既有右儿子又有左儿子  就比较麻烦了
            s = t->right;             //  记录删除节点的右子树根节点
            if(!s->left){
                s->left = t->left;     //如果删除节点的右子树没有左儿子 只要将删除节点的左子树继承给s即可
            }else{
                //需找到删除节点右子树中最左边的节点 即第一个大于删除节点值的节点
                while(s->left){
                    parent = s;          //记录s的父节点
                    s = s->left;
                }

                parent->left = s->right; //若第一个大于删除节点的节点有右子树 继承给其父节点作为其左子树
                s->left = t->left;       //代替删除节点 继承其左子树
                s->right = t->right;     //代替删除节点 继承其右子树
            }

            root = s;                    //更新子树根
        }

        free(t);
    }

    /*               平衡操作              */
    if(!root)
        return NULL;                     //上面递归完之后若根节点都被删了

    //删除操作后可能需要调整高度
    if(GetHeight(root->left) - GetHeight(root->right) > 1){
        //左子树比右子树高 说明删除了右子树中的节点 
        //变向地认为在左子树中插入了节点 需要进行右旋
        if(GetHeight(root->left->left) > GetHeight(root->left->right)){
            return LL_rotate(root);      //左子树的左边更高  需要进行 LL 的右旋
        }else{
            return LR_rotate(root);      //左子树的右边高   需要进行  LR  的右旋
        }
    }else if(GetHeight(root->right) - GetHeight(root->left) > 1){
        //右子树比左子树更高  说明删除的是左子树中的节点
        //变向地认为在右子树插入了节点 需要进行左旋
        if(GetHeight(root->right->right) > GetHeight(root->right->left)){            
            return RR_rotate(root);      //右子树的右边更高 需要进行  RR  的左旋
        }else{
            return RL_rotate(root);      //右子树的左边更高 需要进行  RL  的左旋
        }
    }

    // 更新root的高度
    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    return root;
}

//中序遍历
void ShowInfixOrder(BinaryTree root){
    if(!root)
        return;

    ShowInfixOrder(root->left);
    printf("%d ", root->val);
    ShowInfixOrder(root->right);
}

//层次遍历
void ShowLevelOrder(BinaryTree root){
    if(!root)
        return;

    std::queue q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        for(int i = 0; i val);

            if(t->left)
                q.push(t->left);
            if(t->right)
                q.push(t->right);
        }
        printf("n");
    }
}

int main(){
    BinaryTree T = NULL;
    std::vector v = {12, 9, 18, 16, 20, 15};
    Create_AVL(T, v);

    printf("AVL树中序遍历和层次遍历:n");
    ShowInfixOrder(T);
    printf("nn");
    ShowLevelOrder(T);

    printf("n删除值为9节点的AVL树:n");
    T = Delete_AVL(T, 9);
    ShowInfixOrder(T);
    printf("nn");
    ShowLevelOrder(T);
}

程序测试结果