平衡二叉树 (AVL)

发表于 2020-11-18 更新于 2021-06-10 分类于算法，查找

本文字数： 8.4k

平衡二叉树 —— 任意结点的子树的高度差都小于等于 1 的一棵二叉排序树

数据结构课代码实现之平衡二叉树

简要理解

二叉排序树的缺点

二叉搜索树理想状态下与折半查找的效率相同

但是折半查找长度为 n 的表的判定树唯一，而拥有 n 个结点二叉搜索树的并不唯一

又含有 n 个结点的二叉搜索树的平均查找长度和树的形态有关

最差的情况下，如果先后插入关键字有序时，构成的二叉搜索树就会退化成一个单支树，数的深度为 n，平均查找长度会退化为 (n + 1) / 2 （和顺序查找表相同）

因此需要在构成二叉排序树的过程中进行 “平衡化” 处理，成为二叉平衡树

平衡二叉树的性质

平衡二叉树具有如下性质：

平衡二叉树可为空
如果平衡二叉树不为空树，则每个结点满足：
1. 左、右子树也分别为一棵平衡二叉树
2. 左子树和右子树的深度之差的绝对值不超过 1

平衡二叉树中每个结点都存在一个 平衡因子BF (Balance Factor) 定义为该结点的左子树的深度减去它右子树的深度，易知平衡二叉树上所有结点的平衡因子只可能为 -1、0 和 1

在插入时，可以用结点的 BF 绝对值大于 1 来这个确定以此结点为根结点的最小不平衡子树

我们可以对这个最小不平衡子树进行 “旋转” 操作来使其恢复 “平衡” 并且不破坏其排序性

四个旋转操作

总结了四个 “旋转” 操作，可以应对任何插入与删除结点时失衡的情况：

单向右旋（LL 型）：

单向左旋（RR 型）：

先左旋后右旋（LR 型）：

先右旋后左旋（RL 型）：

插入操作

插入操作使用了递归的方法插入结点，具体过程是先递归查找到插入结点的位置，然后插入结点后，最后一层递归结束，开始一层一层地向上检查父结点是否因为此次插入结点的行为导致失衡 (平衡因子 bf 的绝对值大于 1)，如果失衡则进行相应的平衡操作，直到检查至根节点

插入操作中需要设置一个 bool型变量 taller 来记录每一层递归中进行平衡化操作或者不进行平衡化操作的情况下相应子树的高度是否变高的信息 (在插入结点时，插入的结点所在的子树的高度由 0 变为了 1)，如果增高则由向上一层递归中的结点的 bf 信息判断失衡与否，同时也要更新此结点的 bf 信息与此层递归中相应子树的 taller 信息

删除操作

具体思想与插入操作类似，使用递归查找到删除结点的位置，删除的过程也与二叉排序树的删除操作类似，分为两种情况

该结点只有左右子树，则将该结点的左 (右) 子树的根结点代替此结点即可，不会破坏子树平衡二叉树性质，但需要从要删除的结点开始一层一层地向上检查父结点是否因为此次删除结点的行为导致失衡 (平衡因子 bf 的绝对值大于 1)，如果失衡则进行相应的平衡操作，直到检查至根节点

（这里有个技巧，删除左子树的一个结点导致的失衡，等价于在右子树上插入一个结点导致的失衡，但是在平衡时有一个特殊的情况，在代码中我会注释）
该结点既有左子树又有右子树，则需要利用二叉排序树的性质（中序输出这棵二叉树即为一个由小到大的序列），所以删除该结点，相当于用删除结点的前驱或者后继结点的 data值来代替删除结点的 data值，然后删除前驱或者后继结点

所以就将删除既有左子树又有右子树的结点的问题转化成了删除相应的前驱结点的问题 (我写的是前驱结点，推荐你写后继结点，加深印象)，同时平衡化的处理则同时转化成了解决删除相应的前驱结点产生的不平衡现象的解决问题，易知前驱结点必然不会拥有右子树，所以就转化成了情况一的解决方案

相应地，删除操作中需要设置一个 bool型变量 lower 来记录每一层递归中进行平衡化操作或者不进行平衡化操作的情况下相应子树的高度是否变低的信息 (在删除结点时，删除的结点所在的子树的高度由 1 变为了 0)，如果变低则由向上一层递归中的结点的 bf 信息判断失衡与否，同时也要更新此结点的 bf 信息与此层递归中相应子树的 lower 信息

代码实现

#include<iostream>

#define LH + 1
#define EH 0
#define RH - 1

using namespace std;

typedef struct BSTNode
{
    int data;
    int bf; // 平衡化因子
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

void OnOrder(BSTree T, int l, int r, int cen, int fa) // 中序输出一下结果
{
    if(T)
    {
        
        OnOrder(T->lchild, 1, 0, cen + 1, T->data); 
        if(fa == -1)
            cout << "根节点" << " 该点为：" << T->data << " 层数为：" << cen << " bf为" << T->bf << endl;
        else
        {
            if(l)
                cout << "该点为：" << T->data << " 该节点为 " << fa << " 的左儿子" << " 层数为：" << cen << " bf为" << T->bf << endl;
            if(r)
                cout << "该点为：" << T->data << " 该节点为 " << fa << " 的右儿子" << " 层数为：" << cen << " bf为" << T->bf << endl;
        }
        OnOrder(T->rchild, 0, 1, cen + 1, T->data);
    }
}

bool EQ(int key1, int key2)
{
    if(key1 == key2)
        return true;
    else 
        return false;
}

bool LT(int key1, int key2)
{
    if(key1 < key2)
        return true;
    else
        return false;
}

void R_Rotate(BSTree &p) // 单向右旋操作
{
    BSTree lc = p->lchild;
    p->lchild = lc->rchild;
    lc->rchild = p;
    p = lc;
}

void L_Rotate(BSTree &p) // 单向左旋操作
{
    BSTree rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
}

void LeftBalance(BSTree &T) // 结点所在左子树失衡 两种情况
{
    BSTree lc = T->lchild;
    switch (lc->bf)
    {
        case LH: // 左儿子的左子树高 意味着在左儿子的左子树下插入了一个结点
            T->bf = lc->bf = EH;
            R_Rotate(T); // 单向右旋
            break;
        case RH: // 左儿子的右子树高 意味着在左儿子的右子树下插入了一个结点
        {
            BSTree rd = lc->rchild;
            switch (rd->bf)
            {
                case LH:
                    T->bf = RH;
                    lc->bf = EH;
                    break;
                case RH:
                    T->bf = EH; // 这里建议画图理解吧
                    lc->bf = LH;
                    break;
                case EH:
                    T->bf = EH;
                    lc->bf = EH;
            } 
            rd->bf = EH;
            L_Rotate(T->lchild); // 先左旋后右旋
            R_Rotate(T);
            break;
        }
        case EH: // 这就是删除结点时才会出现的特殊情况 左儿子左右子树等高
            T->bf = LH;
            lc->bf = RH;
            R_Rotate(T); // 子树左子树比右子树高两个高度 直接单向右旋解决问题
            break;
    }
}

void RightBalance(BSTree &T) // 结点所在右子树失衡 两种情况
{
    BSTree rc = T->rchild;
    switch (rc->bf)
    {
        case RH: // 右儿子的右子树高 意味着在右儿子的右子树下插入了一个结点
            T->bf = rc->bf = EH;
            L_Rotate(T); // 单向右旋
            break;
        case LH: // 右儿子的左子树高 意味着在右儿子的左子树下插入了一个结点
        {
            BSTree rd = rc->lchild;
            switch (rd->bf)
            {
                case LH:
                    T->bf = EH;
                    rc->bf = RH;
                    break;
                case RH: // 这里还是建议画图理解吧
                    T->bf = LH;
                    rc->bf = EH;
                    break;
                case EH:
                    T->bf = EH;
                    rc->bf = EH;
                    break;
            } 
            rd->bf = EH;
            R_Rotate(T->rchild); // 先右旋后左旋
            L_Rotate(T);
            break;
        }
        case EH: // 这还是删除结点时才会出现的特殊情况 右儿子左右子树等高
            T->bf = RH;
            rc->bf = LH;
            L_Rotate(T); // 子树右子树比左子树高两个高度 直接单向左旋解决问题
            break;
    }
}

int InsertAVL(BSTree &T, int key, bool &taller)
{
    if(!T) // 在空指针上插入新的结点
    {
        T = (BSTree)malloc(sizeof(BSTNode));
        T->data = key;
        T->lchild = T->rchild = NULL;
        T->bf = EH;
        taller = true; // 新结点所在子树变高
    }
    else
    { // 寻找插入位置的三种情况 当前结点的 data 等于 大于 小于 key
        if(EQ(key, T->data))
        {
            taller = false; // 存在要插入的结点 插入失败 不插入则 taller 置 false  
            return 0;
        }
        if(LT(key, T->data))
        {
            if(!InsertAVL(T->lchild, key, taller))
                return 0; // 如果插入结点存在则 return 0
            if(taller) // 正常情况下检查层次低的子树变高对这一层递归中的结点平衡性的影响
                switch (T->bf)
                {
                    case LH:
                        LeftBalance(T); // 本来左子树就高还往左子树插结点  需要平衡化
                        taller = false; // 平衡化后此层递归的结点所在子树不会变高
                        break;
                    case EH:
                        T->bf = LH; // 本来左右子树等高 往左子树插结点 则左子树高
                        taller = true; // 所以此层递归的结点所在子树会变高
                        break;
                    case RH:
                        T->bf = EH; // 本来右子树高 往左子树插结点 则左右等高
                        taller = false; // 所以此层递归的结点所在子树不会变高
                }
        }
        else
        {
            if(!InsertAVL(T->rchild, key, taller))
                return 0;
            if(taller)
            {
                switch (T->bf)
                {
                    case LH:
                        T->bf = EH; // 本来左子树就高 往右子树插结点 则左右等高
                        taller = false; // 所以此层递归的结点所在子树不会变高
                        break;
                    case EH:
                        T->bf = RH; // 本来左右子树等高 往右子树插结点 则右子树高
                        taller = true; // 所以此层递归的结点所在子树会变高
                        break;
                    case RH:
                        RightBalance(T); // 本来右子树就高还往右子树插结点 需要平衡化
                        taller = false; // 平衡化后此层递归的结点所在子树不会变高
                        break;
                }
            }
        }
        return 1;
    }
}

BSTree root;

bool DeleteAVL(BSTree &T, int key, bool &lower);

void getRoot(BSTree T)
{
    root = T;
}

void Delete(BSTree &p) // 删除操作 存在三种情况
{
    BSTree q;
    if(!p->lchild) // 删除结点没有左子树
    {
        q = p;
        p = p->rchild; // 直接用结点右子树的根结点代替此结点
        free(q);
    }
    else if(!p->rchild) // 删除结点没有右子树
    {
        q = p;
        p = p->lchild; // 直接用结点左子树的根结点代替此结点
        free(q);
    }
    else // 删除结点既有左子树又有右子树
    {
        q = p;
        BSTree t = p; // 删除前驱结点时失衡调整会更改 p指针 所指向的结点 此处保存一下
        BSTree s = p->lchild;
        while(s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        BSTree tmp = s->lchild; // 删除前驱结点s 需要保存 s的左儿子
        int x = s->data; // 以及保存 s的data
        bool lower = false;
        DeleteAVL(root, x, lower);
        if(q != t)
            q->rchild = tmp;
        else
            q->lchild = tmp;
        t->data = x; // 用前驱结点的 data 代替 删除结点的data
    }
}

bool DeleteAVL(BSTree &T, int key, bool &lower)
{
    if(!T) 
    {
        lower = false; // 找不到删除的结点 lower 置 false
        return false; // 删除失败 返回false
    }
    else
    { // 寻找删除结点的三种情况 当前结点的 data 等于 大于 小于 key
        if(EQ(key, T->data))
        {
            Delete(T); // 找到删除的结点 进行删除操作
            lower = true; // 删除结点所在的相应子树高度变低
        }
        else if(LT(key, T->data))
        {
            if(!DeleteAVL(T->lchild, key, lower))
                return false; // 如果不存在删除结点存在则 return false
            if(lower)
            {
                switch (T->bf)
                {
                    case EH:
                        T->bf = RH; // 本来左右子树等高 删除左子树上结点 右子树高
                        lower = false; // 所以此层递归的结点所在子树不会变低
                        break;
                    case LH:
                        T->bf = EH; // 本来左子树高 删除左子树上结点 左右子树等高
                        lower = true; // 所以此层递归的结点所在子树会变低
                        break;
                    case RH:
                        RightBalance(T); // 本来右子树高 删除左子树上结点 需要平衡化
                        lower = true; // 平衡化后此层递归的结点所在子树会变低
                        break;
                }
            }
        }
        else
        {
            if(!DeleteAVL(T->rchild, key, lower))
                return false; // 如果不存在删除结点存在则 return false
            if(lower)
            {
                switch (T->bf)
                {
                    case EH:
                        T->bf = LH; // 本来左右子树等高 删除右子树上结点 左子树高
                        lower = false; // 所以此层递归的结点所在子树不会变低
                        break;
                    case RH:
                        T->bf = EH; // 本来右子树高 删除右子树上结点 左右子树等高
                        lower = true; // 所以此层递归的结点所在子树会变低
                        break;
                    case LH:
                        LeftBalance(T); // 本来左子树高 删除右子树上结点 需要平衡化
                        lower = true; // 平衡化后此层递归的结点所在子树会变低
                        break;
                }
            }
        }
        return true;
    }
}

int main()
{
    BSTree T;
    T = NULL;
    int num;
    cout << "请输入树的结点数：" << endl;
    cin >> num;
    cout << "依次输入每个结点的 data 值，空格分开" << endl;
    for(int i = 0;i < num;i++)
    {
        int key;
        cin >> key;
        bool taller = false;
        InsertAVL(T, key, taller);
    }
    cout << "构建的平衡二叉树为：" << endl;
    OnOrder(T, 0, 0, 1, -1);
    cout << "请输入删除的结点数：" << endl;
    cin >> num; 
    cout << "依次输入删除的结点的data值，空格分开" << endl;
    for(int i = 0;i < num;i++)
    {
        getRoot(T);
        int key;
        cin >> key;
        bool lower = false;
        DeleteAVL(T, key, lower);
    } 
    cout << "删除后的平衡二叉树为：" << endl;
    OnOrder(T, 0, 0, 1, -1);
    return 0;
}