什么是平衡二叉树（AVL） (2)

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

5.1 左旋

图 5.1.1

以图 5.1.1 为例，加入新节点 99 后， 节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2。为保证树的平衡，此时需要对节点 66 做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：

（1）节点的右孩子替代此节点位置
（2）右孩子的左子树变为该节点的右子树
（3）节点本身变为右孩子的左子树

整个操作流程如动图 5.1.2 所示。

动图 5.1.2

节点的右孩子替代此节点位置 —— 节点 66 的右孩子是节点 77 ，将节点 77 代替节点 66 的位置

右孩子的左子树变为该节点的右子树 —— 节点 77 的左子树为节点 75，将节点 75 挪到节点 66 的右子树位置

节点本身变为右孩子的左子树 —— 节点 66 变为了节点 77 的左子树

5.2 右旋

右旋操作与左旋类似，操作流程为：

（1）节点的左孩子代表此节点
（2）节点的左孩子的右子树变为节点的左子树
（3）将此节点作为左孩子节点的右子树。

动图 5.2.1

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

假设一颗 AVL 树的某个节点为 A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入节点的情况分为以下四种：

插入方式 描述 旋转方式
LL   在 A 的左子树根节点的左子树上插入节点而破坏平衡   右旋转  
RR   在 A 的右子树根节点的右子树上插入节点而破坏平衡   左旋转  
LR   在A的左子树根节点的右子树上插入节点而破坏平衡   先左旋后右旋  
RL   在 A 的右子树根节点的左子树上插入节点而破坏平衡   先右旋后左旋  

具体分析如下：

6.1 A的左孩子的左子树插入节点(LL)

只需要执行一次右旋即可。

动图 6.1

实现代码如下：

//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)

只需要执行一次左旋即可。

动图 6.2