平衡二叉树（AVL）图（修订补充版）

以图5.1.1为例，添加新节点99后，节点66的左子树的高度为1，右子树的高度为3。此时，平衡系数为-2。为了保证树的平衡，此时必须对节点66进行旋转。由于右子树的高度高于左子树，因此对该节点进行左旋转操作。过程如下：

(1) 该节点的右子节点改变该节点的位置。 (2) 右孩子的左子树成为该节点的右子树 (3) 节点本身成为右孩子的左子树

整个操作过程如动画5.1.2所示。节点

• 的右子节点替换了该节点的位置 - 节点 66 的右子节点是节点 77，节点 77 替换了节点 66 的位置。右子节点
• 的左子树成为节点 - 节点 77 的左子树是节点 75。将节点 75 移动到节点 66 的右子树位置
• 节点本身成为右子树的左子树 - 节点 66 成为节点 77 的左子树

5.2 右旋转

右旋转操作与左旋转相同。操作过程为：

(1) 该节点的左孩子代表该节点 (2) 该节点的左孩子的右子树成为该节点的左子树 (3) 将该节点视为右子树。从左子节点开始。

6。向 AVL 树插入节点的四种方式

假设 AVL 树的特定节点为 A，有四种操作会导致 A 左右子树的高度差大于 1，因此破坏树原有的AVL平衡。平衡二叉树插入节点有四种情况：

具体分析如下：

6.1 左孩子A的左子树插入节点（LL）

只需要右旋转一次。

实现代码如下：

//LL型调整函数
//返回:新父节点
Tree LL_rotate(Tree node){
    //node为离操作节点最近的失衡的节点
    Tree parent=NULL,son;
    //获取失衡节点的父节点
    parent=node->parent;
    //获取失衡节点的左孩子
    son=node->lchild;
    //设置son节点右孩子的父指针
    if (son->rchild!=NULL)  son->rchild->parent=node;
    //失衡节点的左孩子变更为son的右孩子
    node->lchild=son->rchild;
    //更新失衡节点的高度信息
    update_depth(node);
    //失衡节点变成son的右孩子
    son->rchild=node;
    //设置son的父节点为原失衡节点的父节点
    son->parent=parent;
    //如果失衡节点不是根节点，则开始更新父节点
    if (parent!=NULL){
        //如果父节点的左孩子是失衡节点，指向现在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
             //父节点的右孩子是失衡节点
              parent->rchild=son;
        }
     }
    //设置失衡节点的父亲
    node->parent=son;
    //更新son节点的高度信息
    update_depth(son);
    return son;
}

复制代码

6.2 在A的右子树的右子树中插入一个节点（RR）

只需执行一次左旋即可。

实现代码如下：

//RR型调整函数
//返回新父节点
Tree RR_rotate(Tree node){
    //node为离操作节点最近的失衡的节点
    Tree parent=NULL,son;
    //获取失衡节点的父节点
    parent=node->parent;
    //获取失衡节点的右孩子
    son=node->rchild;
    //设置son节点左孩子的父指针
    if (son->lchild!=NULL){
          son->lchild->parent=node;
    }
    //失衡节点的右孩子变更为son的左孩子
    node->rchild=son->lchild;
    //更新失衡节点的高度信息
    update_depth(node);
    //失衡节点变成son的左孩子
    son->lchild=node;
    //设置son的父节点为原失衡节点的父节点
    son->parent=parent;
    //如果失衡节点不是根节点，则开始更新父节点
    if (parent!=NULL){
        //如果父节点的左孩子是失衡节点，指向现在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
            //父节点的右孩子是失衡节点
            parent->rchild=son;
        } 
    }
    //设置失衡节点的父亲
    node->parent=son;
    //更新son节点的高度信息
    update_depth(son);
    return son;
}
复制代码

6.3 将A的左子树的右子树插入到节点（LR）

如果A的右子树E将B的左子节点插入到节点F、A就会不平衡，如图： 平衡因子

A为2。如果仍然按照正确的旋转进行调整，变化后的图形如下：

调整后的右旋转，发现调整后树仍然不平衡，说明在这种情况下，进行简单的右旋转操作无法重新平衡树。那么这种插入方法需要两步操作，这样旋转之后，是原根节点左孩子的右孩子就变成了新的根节点。

(1) 对不平衡节点A的左子节点B进行左转操作，即上述RR条件操作。 (2)对不平衡节点A进行右转操作，即上述LL条件操作。

调整过程如下：

也就是说，经过这两步之后，原根节点的左子节点的右子节点E成为新的根节点。

代码实现：

//LR型，先左旋转，再右旋转
//返回：新父节点
Tree LR_rotate(Tree node){
    RR_rotate(node->lchild);
    return LL_rotate(node);
}
复制代码

6.4 在A的右孩子的左子树中插入节点（RL）

右孩子插入左节点的过程与插入右孩子的过程相同左子节点的节点。还需要两步操作，这样旋转后，原根节点的右孩子的左孩子就是新的根节点。

(1) 对不平衡节点A的右孩子C进行右转操作，即上面LL情况的操作。 (2)对不平衡节点A进行向左操作，即上述RR条件操作。

也就是说，经过这两步之后，原根节点的右子节点的左子D节点就成为了新的根节点。

代码实现：

//RL型，先右旋转，再左旋转
//返回:新父节点
Tree RL_rotate(Tree node){
    LL_rotate(node->rchild);
    return RR_rotate(node);
}
复制代码

附加：

以上四种插入方式的代码实现附加代码如下：❀

//更新当前深度
void update_depth(Tree node){
    if (node==NULL){
        return;
    }else{
        int depth_Lchild=get_balance(node->lchild); //左孩子深度
        int depth_Rchild=get_balance(node->rchild); //右孩子深度
        node->depth=max(depth_Lchild,depth_Rchild)+1;
    }
}

//获取当前节点的深度
int get_balance(Tree node){
    if (node==NULL){
         return 0;
    }
    return node->depth;
}

//返回当前平衡因子
int is_balance(Tree node){
    if (node==NULL){
         return 0;
    }else{
         return get_balance(node->lchild)-get_balance(node->rchild); 
    }
}
复制代码

6。代码如下： 首先找到最小不平衡树，然后找到包含的不平衡类别，然后根据固定程序执行操作。

LL、LR、RR、RL 实际上已经给新的根节点指明了方向。例如，LR类型的最后一个根节点是原始根的左子节点的右子节点，RL类型的最后一个根节点是原始根的左子节点。只要记住这四种情况，你就能很快总结出整个情况。

维持平衡二叉树最难的部分是维持平衡因子。我们鼓励读者根据小吴提供的图片和动画自己画出，让他们能够感性地理解操作。

7。 AVL树删除节点的四种方式

AVL树和二叉搜索树的删除操作是一样的，分为四种情况：

（1）删除叶子节点（2）删除只有左子树的节点 (3) 删除的节点只有右子树 (4) 删除的节点有左子树和右子树

只是删除节点后需要再次检查 AVL 树 是正确。同时，删除操作后的平衡修正与插入操作的区别在于，插入操作后，只需要修正栈中第一个出现的不平衡节点，而删除操作则需要修正所有的不平衡节点。堆栈中不平衡的节点。不平衡节点。

删除操作的一般步骤如下：

• 根据前面三个条件尝试删除一个节点，并将访问的节点压入堆栈。
• 如果删除尝试成功，将依次检查栈顶节点的平衡状态。如果遇到不平衡节点，则进行轮换和平衡，直到栈为空。
• 如果删除尝试失败，则属于第四种情况。此时，找到被删除节点右子树的最小节点并将其删除，并继续将访问的节点压入堆栈。
• 检查平衡状态，轮流修正栈顶节点，直至栈为空。

为了纠正删除操作带来的不平衡，可以这样理解：对左子树或右子树进行删除操作与对右子树或左子树进行插入操作相同，然后选择合适的一。根据四种插入条件之一。旋转就好了。 ？追踪并计算父节点是否不平衡；

③。如果父节点不平衡，则继续向上搜索，计算父节点的父节点是否不平衡……重复判断②，直到根节点；如果向上计算时发现不平衡，则

④。如果父节点不平衡，则确定不平衡类型[LL，LR，RR，RL]，并进行相应的处理。平衡处理。如果平衡过程完成后，发现以父节点为ROOT节点的树的高度发生了变化，则继续计算②；如果与以父节点为根节点的原始树的高度一致，则可以说明父节点的父节点与祖先节点的平衡因子不会改变，因此可以退出该过程；

具体数值演示：

7.2 & 7.3 删除的节点只有左子树或右子树

处理步骤：

①。将左子树（右子树）替换为原节点C的位置；

②。删除节点C后，以C的父节点B为起始推理点，向上搜索。计算各个节点（父节点、祖先节点）是否不平衡；

③。如果父节点不平衡，则继续查找判断父节点的父节点是否不平衡……重复判断②，直到根节点；如果向上计算时发现不平衡，则

④。如果父节点不平衡，则确定不平衡类型[LL，LR，RR，RL]，并进行相应的处理。平衡处理。如果平衡过程完成后，发现以父节点为ROOT节点的树的高度发生了变化，则继续计算②；如果与以父节点为根节点的原始树的高度一致，则可以说明父节点的父节点与祖先节点的平衡因子不会改变，因此可以退出该过程；

7.4删除的节点有左子树和右子树

处理步骤：

①，找到删除的节点删除B节点和BLR替换节点（这里选择BLR后继节点后继）；

②，将替换节点的BLR值赋给节点B，则替换节点BLR的左孩子BLRL改变替换节点BLR的位置；

③，以BLR的父节点BL为起始推理点，向上查找计算父节点或祖先节点是否不平衡；

④，如果父节点不平衡的话，继续向上搜索，计算父节点的父节点是否不平衡...重复判断③，直到ROOT节点；如果向上计算过程中发现不平衡，则进行

⑤。如果父节点不平衡，则确定不平衡类型[LL，LR，RR，RL]，并平衡。如果平衡过程完成后，发现以父节点为ROOT节点的树的高度发生了变化，则继续计算②；如果与以父节点为根节点的原始树的高度一致，则可以说明父节点的父节点与祖先节点的平衡因子不会改变，因此可以退出该过程；

注：这里，小吴没有提供AVL删除操作的代码，也没有提供修复平衡的动画。 ，由于我不打算讨论，所以更复杂的删除操作流程将在下一个红黑树中讨论。

总结

从AVL插入和删除操作可以看出，平衡二叉树的优点是它不是普通二叉搜索树的最坏情况，即退化为链表结构，但要保证高度平衡（对称），动态插入和删除的成本也增加。

AVL旋转问题看起来很复杂，但如果你自己用笔和纸操作一下，其实很容易理解。

作者：小吴哥
链接：https://juejin.im/post/5c550b41f265da2d8e70bc35
来源：掘金❀商业转载请联系作者授权。非商业转载请注明出处。