2022-08-13 22:03 已编辑湖南师范大学 Java

关注

C++手撕AVL树

零、前言

本章主要讲解map和set的底层结构平衡二叉搜索树的一种-AVL树的特性及其实现

一、AVL树的概念

引入：

map/multimap/set/multiset其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷

假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)

因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现

概念：

对于数据有序或接近有序二叉搜索树将退化为单支树的情况，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL

树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

示图：

注：如果一棵二叉搜索树是高度可保持在1(-1/0/1)，则非常接近完全二叉树，搜索时间复杂度O(logN)

二、AVL树结点定义

为了方便找到子树对应的父亲节点，这里我们选择使用三叉链结构

代码实现：

template<class T>
struct AVLTreeNode
{
    //三叉链
    AVLTreeNode<T>* _left;
    AVLTreeNode<T>* _right;
    AVLTreeNode<T>* _parent;

    int _bf;//平衡因子
    T _kv;//T可以是key也可以是pair<K,V>类型便于封装成map或set

    AVLTreeNode(const T& t)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)
        ,_kv(t)
    {}
};

三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树

那么AVL树的插入过程：

首先按照二叉搜索树的方式插入新节点

待插入结点的key值比当前结点小就插入到该结点的左子树
待插入结点的key值比当前结点大就插入到该结点的右子树
待插入结点的key值与当前结点的key值相等就插入失败

示例：插入12

插入后则向上调整当前结点到根路径上祖先结点的平衡因子

示图：

平衡因子数值=右子树高度-左子树的高度

平衡因子更新规则：

1.如果新增结点在祖父节点的左子树中，则父节点平衡因子数值减1

2.如果新增结点在祖父节点的右子树中，则父节点平衡因子数值加1

平衡因子更新后处理规则：

1.更新后平衡因子为1或-1，那么说明该平衡因子更新前为0，子树的高度发生变化，则也会影响父亲结点的平衡因子，继续向上更新平衡因子

2.更新后平衡因子为0，那么说明该平衡因子更新前为1或-1，子树的高度未发生变化，则也不会影响父亲结点的平衡因子，停止向上更新平衡因子

3.更新后平衡因子为2或-2，那么当前子树不符合AVL树的规则，需要进行旋转子树进行调节高度

注：更新平衡因子之前，该树本身就满足AVL树的规则，平衡因子为1或0或-1

示图：

实现代码：

pair<Node*, bool> Insert(const pair<K,V>& kv)
{
    if (_root == nullptr)//空树的情况
    {
        _root = new Node(kv);
        return make_pair(_root, true);
    }
    //插入需要链接父子节点，但是插入的位置是空节点，需要另一个指针记录父结点
    Node* cur = _root, *parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else//找到了相同的
        {
            return make_pair(cur,false);
        }
    }
    //找到插入位置，创建链接节点
    cur = new Node(kv);
    Node* newnode = cur;//记录新结点地址，便于返回
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;

    //向上更新平衡因子
    while (cur != _root)
    {
        if (parent->_right == cur)
        {
            parent->_bf++;
        }
        else
        {
            parent->_bf--;
        }

        if (parent->_bf == 0)//子树高度不变，不影响上面路径的结点平衡因子
        {
            break;
        }
        else if (parent->_bf == 1 || parent->_bf == -1)//子树高度改变，继续向上更新节点平衡因子
        {
            cur = parent;
            parent = parent->_parent;
        }
        else if (parent->_bf == 2 || parent->_bf == -2)//子树已经不平衡了,需要进行旋转处理
        {
            if (parent->_bf == -2)
            {
                if (cur->_bf == -1)//右单旋
                {
                    RotateR(parent);
                }
                else//左右双旋
                {
                    RotateLR(parent);
                }
            }
            else
            {
                if (cur->_bf == 1)//右单旋
                {
                    RotateL(parent);
                }
                else//右左双旋
                {
                    RotateRL(parent);
                }
            }
            break;
        }
        else//已经出错了
        {
            assert(false);
        }
    }
    return make_pair(newnode, true);
}

四、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡

根据节点插入位置的不同，AVL树的旋转分为四种：

新节点插入较高右子树的右侧---右右：左单旋

1、左单旋

抽象示图：

注意：

上图在插入前AVL树是平衡的，新节点插入到60的右子树(注意：此处不是有孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡
要让30平衡，只能将30右子树的高度减少一层，左子树增加一层，即将右子树往上提，这样30转下来，因为30比60大=小，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可
对于a,b,c都是符合AVL树且高度为h的树的一种，这里不具体表示，以抽象表示各种情况，对于以下抽象图示也是如此

在旋转过程中，有以下几种情况需要考虑：

60节点的左孩子可能存在，也可能不存在

30可能是根节点，也可能是子树：如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树，需要更新父结点的左右结点地址

旋转后，子树得到平衡，两个旋转结点的平衡因子更新为0，而高度没有改变，不用再向上更新结点平衡因子

实例示图：

实现代码：

// 左单旋
void RotateL(Node* parent)
{
    //记录节点信息
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentP = parent->_parent;

    //修改链接关系
    parent->_right = subRL;
    if (subRL)//避免为空节点的情况
        subRL->_parent = parent;

    subR->_left = parent;
    parent->_parent = subR;

    //讨论父节点的情况
    if (parent == _root)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parentP->_left == parent)
        {
            parentP->_left = subR;
        }
        else
        {
            parentP->_right = subR;
        }
        subR->_parent = parentP;
    }

    //更新平衡因子
    subR->_bf = parent->_bf = 0;
}

新节点插入较高左子树的左侧---左左：右单旋

2、右单旋

注：具体思路和步骤可以参考左单旋

抽象示图：

实例示图：

实现代码：

// 右单旋
void RotateR(Node* parent)
{
    //记录节点信息
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentP = parent->_parent;

    //修改链接关系
    parent->_left = subLR;
    if (subLR)//避免为空节点的情况
        subLR->_parent = parent;

    subL->_right = parent;
    parent->_parent = subL;

    //讨论父节点的情况
    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parentP->_left == parent)
        {
            parentP->_left = subL;
        }
        else
        {
            parentP->_right = subL;
        }
        subL->_parent = parentP;
    }

    //更新平衡因子
    subL->_bf = parent->_bf = 0;
}

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

3、左右双旋

抽象示图：

注意：

将双旋变成单旋后再旋转，即先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新（并不都为0，具体情况具体分析）

复用单旋会把其他情况都给处理，例如子树是否为空，当前不平衡结点为根结点还是子树结点

对于h高度的子树，h满足大于等于0，当h=0时，插入新节点就是60

左右双旋可以看做是60做当前树的根结点，并将左子树给给30结点，将右子树给给90结点

旋转后更新平衡因子具有三种情况：

插入结点就是不平衡结点的subLR（左子结点的右子结点），30,60,90都更新为0

插入结点为不平衡结点的subLR的左子结点，30,60更新为0，90更新为1

插入结点就是不平衡结点的subLR的右子节点，90,60更新为0，30更新为-1

实例示图：h为0的情况

实现代码：

// 左右双旋
void RotateLR(Node* parent)
{
    //记录节点地址和平衡因子
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    int bf = subLR->_bf;
    //旋转
    RotateL(subL);
    RotateR(parent);

    //处理平衡因子
    if (bf == -1)//新增节点为subLR的左子树
    {
        subLR->_bf = 0;
        parent->_bf = 1;
        subL->_bf = 0;
    }
    else if (bf == 1)//新增节点为subRL的右子树
    {
        subL->_bf = -1;
        parent->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 0)//新增节点就是subRL
    {
        subLR->_bf = 0;
        parent->_bf = 0;
        subL->_bf = 0;
    }
    else //旋转之前就已经存在错误了
    {
        assert(false);
    }
}

新节点插入较高右子树的左侧---右左：先右单旋再左单旋

4、右左双旋

抽象示图：

注：具体情况可以参考左右双旋

实例示图：

实现代码：

// 右左双旋
void RotateRL(Node* parent)
{
    //记录节点地址和平衡因子
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    int bf = subRL->_bf;
    //旋转
    RotateR(subR);
    RotateL(parent);

    //处理平衡因子
    if (bf == -1)//新增节点为subLR的左子树
    {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 1;
    }
    else if (bf == 1)//新增节点为subLR的右子树
    {
        subRL->_bf = 0;
        parent->_bf = -1;
        subR->_bf = 0;
    }
    else if (bf == 0)//新增节点就是subLR
    {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 0;
    }
    else //旋转之前就已经存在错误了
    {
        assert(false);
    }
}

5、总结

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑：

pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当SubR的平衡因子为1时，执行左单旋

当SubR的平衡因子为-1时，执行右左双旋

pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当SubL的平衡因子为-1是，执行右单旋

当SubL的平衡因子为1时，执行左右双旋

从视角上来看，当旋转相关结点成直线，则进行单旋；当旋转相关结点成折线，则进行双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制

要验证AVL树可以分两步：

验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

实现代码：

void _InOrder(Node* root)
{
    if (root == nullptr)
        return;

    _InOrder(root->_left);
    cout << root->_kv.first << " : " << root->_kv.second << endl;
    _InOrder(root->_right);
}

验证其为平衡树

每个结点子树高度差的绝对值不超过1(注意结点中如果没有平衡因子)以及结点的平衡因子是否计算正确

实现代码：

//验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* root)
{
    //空树
    if (root == nullptr)
        return true;
    //比较高度
    int heightL = _Height(root->_left);
    int heightR = _Height(root->_right);
    //检查平衡因子是否有误
    if (heightR - heightL != root->_bf)
    {
        cout << "平衡因子错误：" << root->_kv.first << endl;
        return false;
    }

    return abs(heightR - heightL) < 2
        && _IsAVLTree(root->_left)
        && _IsAVLTree(root->_right);//递归检查左右子树
}
//高度
size_t _Height(Node* root)
{
    //空节点
    if (root == nullptr)
        return 0;

    size_t left = _Height(root->_left);
    size_t right = _Height(root->_right);

    return left > right ? left + 1 : right + 1;
}