最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天快播：[数据结构] AVL树

来源：博客园

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 < val){                root = RR_rotate(root);  //如果插入位置为右儿子的右子树RR，左旋            }else{                root = RL_rotate(root);  //如果插入位置为右儿子的左子树RL，先右旋再左旋            }        }    }    //更新高度    root->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 < val){        root->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 Landistypedef 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);elsereturn 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 < val){root = RR_rotate(root);  //如果插入位置为右儿子的右子树RR，左旋}else{root = RL_rotate(root);  //如果插入位置为右儿子的左子树RL，先右旋再左旋}}}    //更新高度root->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 < val){root->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 < n; i++){BinaryTree t = q.front();q.pop();printf("%d ", t->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("\n\n");    ShowLevelOrder(T);    printf("\n删除值为9节点的AVL树:\n");    T = Delete_AVL(T, 9);    ShowInfixOrder(T);    printf("\n\n");    ShowLevelOrder(T);}

程序测试结果

关键词： 删除节点 插入节点