【C++】AVL树（平衡搜索二叉树）

慕雪的小助手正在绞尽脑汁···

慕雪小助手的总结

LongCat-Flash-Chat

在上一篇C++博客中，讲述了关于搜索二叉树以及KVL树的实现。也提到了搜索二叉树的最坏情况：插入的数据已经有序。

而本篇博客涉及到的AVL树，又称平衡搜索二叉树。就是为了解决搜索二叉树的最坏情况而生的。

[TOC]

1. 什么是AVL树

二叉搜索树虽然缩短了查找的效率，但是数据有序的时候，就会出现一边非常长的情况，导致原本的O(logN)时间复杂度被迫变成了O(N)

平衡树也是搜索二叉树，其引入了一个平衡因子的概念，用于控制搜索二叉树的平衡。它会保证左右子树的高度之差（绝对值）不超过1。当新插入节点导致高度之差超过1时，便会触发旋转，使得树的高度降低。

简单说来：AVL树能保证两边高度的相对平衡，这样就稳定了二叉搜索树的效率

1.1 二叉搜索树的性质

一颗AVL树或空树，其有以下性质

它的左右子树是AVL树
左右子树的高度之差的绝对值不超过1

这里引入平衡因子来方便我们控制二叉树的高度。每一个节点都会有一个平衡因子，它的值是1/0/-1。如果平衡因子的值超过了1，那么说明这个节点的子树已经不平衡，需要进行旋转。

实际上，AVL树不一定非要用平衡因子。我们可以用计算树的高度的方式来确认平衡因子，但是这样需要遍历左右子树，时间复杂度较高

2. 实现一颗AVL树

2.1 AVL树的节点

基本的概念理解之后，我们需要设计出一个节点的结构来。关于各个值的含义，可以参考下方的注释

平衡搜索二叉树是一个“三叉链”。这代表每一个节点都有左右孩子，还有一个prev指针指向它的父节点。
为了标识树是否平衡，准确来说是某个节点的左右子树是否平衡。我们需要引入一个“平衡因子”来进行判断，方便我们控制平衡

左右子树高度相同 0

左子树高于右子树 -1

右子树高于左子树 1

template<class K,class V>
struct AVLTreeNode
{
    pair<K, V> _kv;//键值对
    AVLTreeNode<K, V>* _left;//左子树
    AVLTreeNode<K, V>* _right;//右子树
    AVLTreeNode<K, V>* _parent;//父节点

    // 右子树-左子树的高度差
    int _bf;  // 平衡因子

    AVLTreeNode(const pair<K, V>& kv)
        :_kv(kv),
        _left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _bf(0)
    {}
};

关于键值对的内容，在上篇博客的KVL树中有提到过【传送门】

2.2 AVL树的插入（重要）

因为AVL需要控制树的高度，其插入的时候就没有KVL树那么方便了。我们每次插入之后，都需要向上更新并判断树的平衡因子是否正常

先来理清一下思路:

如果是空树，new一个新节点交给root，无需进行后续操作
插入新节点的时候，利用搜索二叉树的规则（在这里我采用了左小右大的规则）来找到新节点应该插入的位置，直接进行插入
插入之后，需要向上更新平衡因子（利用父节点parent）
- 如果该插入节点在父节点的右边，平衡因子+1
- 如果在该节点的左边，平衡因子-1。
更新了平衡因子之后，需要及时进行判断。如果平衡因子等于0，则不需要继续往上更新。如果平衡因子的绝对值大于1，说明当前就需要旋转了

根据这个思路，我们可以先写出插入的一个基本框架

bool Insert(const pair<K, V>& kv)
{
    //判断root为空，即空树
    if (_root == nullptr)
    {
        _root = new Node(kv);
        return true;
    }
    //kv树的操作
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
           //利用key来判断，寻找待插入的位置
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else{
            return false;
        }
    }
    //找到位置后插入节点
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;

    //插入之后需要向上更新平衡因子
    while (parent)
    {
        if (cur == parent->_left) {
            parent->_bf--;//左-1
        }
        else{
            parent->_bf++;//右+1
        }

        //更新了之后，需要判断是否继续更新，还是需要旋转
        if (parent->_bf == 0) {
            break;//为0代表高度没有变化，不需要继续更新
        }
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            cur = cur->_parent;//向上更新
            parent = parent->_parent;
        }
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            //旋转
        }
        else
        {
            //插入之前AVL就存在不平衡子树
            assert(false);
        }
    }
    return true;
}

其中最复杂的部分：旋转，需要拿出来单独讲解一番

下面是一个最简单的二叉树进行插入之后，平衡因子的变化。

因为搜索二叉树需要保证两边的高度之差不大于1，所以此时我们的树还没有违背AVL树的规则。

可如果我们继续往右子树插入节点呢？

可以看到，最后一颗子树的根节点的平衡因子为2，超过了1。此时两边子树的高度差为2，需要我们进行旋转操作

2.2.1 左/右单旋

为了简化，我们把上图的插入情况直接简化为下面的样子

当我们在这棵树高度较高的那一侧的边缘插入的时候，就需要进行单旋。

比如右边高，就是在最右边的叶子处插入时需要进行单旋

单旋的思路很好理解，下面以左单旋为例（蓝色代表新增节点）

这里我们设置了3个不同的节点，分别是prev起始节点（即平衡因子大于1的节点）以及它的右子树subR、右子树的左子树subRL（即图中的b子树）

需要做的操作，就是把subRL链接给prev的右，再将prev链接到subR的左
因为subRL在prev的右侧，其的值肯定大于prev，所以这样链接是不会破坏搜索二叉树的结构的。

旋转完成之后，我们需要把prev和subR的平衡因子都更新为0

右单旋的操作和左单旋的思路完全相同，只不过方向相反

思路搞定了，下面就来写一个代码吧！

void RotateL(Node* parent)//左单旋
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    //用来记录当前parent的父亲，最后的链接需要
    Node* ppNode = parent->_parent;

    prev->_right = subRL;
    if (subRL != nullptr)
    {//不为空才能进行parent操作
        subRL->_parent = prev;
    }

    subR->_left = prev;
    prev->_parent = subR;

    if (prev == _root)
    {//单独操作为根节点的情况
        //subR->_parent = nullptr;
        _root = subR;
        _root->_parent = nullptr;
    }
    else
    {
        if (prev == ppNode->_left) {
            ppNode->_left = subR;
        }
        else {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode;
    }
    //默认全都改成0
    subR->_bf = parent->_bf = 0;
}

右单旋的代码和这个类似，这里就不贴出来了

完整代码可以到我的代码仓库里面看哦！【Gitee】

旋转的代码写好了，我们现在还需要了解的是，什么时候需要进行单旋？

看图可以得知，当prev的平衡因子为-2，subL的平衡因子为-1的时候，需要进行一次右单旋

同理，我们可以推断出一个结论，那就是当父节点的平衡因子的绝对值超过1，其左/右边节点的平衡因子为1且和父节点平衡因子的正负相同时，需要向另外一个方向进行单旋。

左单旋就是父节点为2，其右子树为1，需要向另外一个方向左进行单旋

需要注意的是，虽然图里面画出来的prev是根节点，但实际上进行单旋的时候，prev可能是另外一棵树的子树。在单旋的处理过程中，我们必须要保存prev的父节点，并重新链接至subR

//插入函数的旋转部分
else if (parent->_bf == 2 || parent->_bf == -2)
{
    if (parent->_bf == 2 && cur->_bf == 1)
    {
        RotateL(parent);
    }
    else if (parent->_bf == -2 && cur->_bf == -1)
    {
        RotateR(parent);
    }
    else
    {
        //……
    }
    break;
}

我们用下面的代码进行测试

void TestAVLTree1()
{
    int a[] = {9,8,7,6,5,4,3,2,1 };
    AVLTree<int, int> t;
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));
    }
    t.InOrder();
    cout << endl;
}

进行中序打印，可以获取道下面的结果。可以看到数据已经有序

在VS2019的调试窗口中可以看到，我们厂家的这棵树是符合平衡搜索二叉树的性质的

2.2.2 左右/右左双旋

上面的情况还算容易，一次单旋就能解决。那如果我们插入不有序的数据呢？

可以看到中序打印的结果已经有序，可它符合平衡二叉树的规则吗？

再插入一个25，会发现触发了断言，说明AVL树的规则被破坏了

就好比下面的这种情况，我们是以15 6 7这种非有序方式插入的，就会出现单旋完全处理不了的情况

如果进行单旋会发生什么呢？

可以看到，毫无变化。旋转了之后的节点依旧是违反AVL树的规则

这时候我们就需要进行两次循环了！

24-03-27备注：下图中的节点应该有问题，左下角的图中30和10的位置应该更换，右下角的图中，30应该是根，10是右子树，20是左子树。

概念理解了之后，我们就可以直接来写代码了。

因为本质上就是两次单旋，所以我们可以直接复用之前写好的单旋代码

void RotateLR(Node* parent)//左右
{
    RotateL(parent->_left);
    RotateR(parent);
}

但事情远没有这么简单！

在2.2.1单旋的操作中，我们旋转完毕后会把prev和subL的平衡因子都改成了0。在这种双旋的情况下，全改成0显然不符合要求。

下面的情况，我们就需要在旋转之后，把10的平衡因子改成-1，20和30的平衡因子改成0

双旋的情况分为下面3种，我们可以直接用紫色框中所指的这个节点来判断属于哪一种情况，再针对性的处理！

处理之后的结果如下

其代码逻辑如下

//这种双旋转的情况，基本如下
//   9
// 7
//   8
//必须要双旋转才能解决问题
void RotateLR(Node* parent)//左右
{
    Node* prev = parent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(parent->_left);
    RotateR(parent);

    if (bf == 0)
    {
        prev->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 1)
    {
        subL->_bf = -1;
        prev->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        subL->_bf = 0;
        prev->_bf = 1;
        subLR->_bf = 0;
    }
    else {
        assert(false);
    }
}
void RotateRL(Node* parent)//右左
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(parent->_right);
    RotateL(parent);

    if (bf == 0)
    {
        prev->_bf = 0;
        subR->_bf = 0;
        subRL->_bf = 0;
    }
    else if (bf == -1)
    {
        subR->_bf = 1;
        prev->_bf = 0;
        subRL->_bf = 0;
    }
    else if (bf == 1)
    {
        subRL->_bf = 0;
        subR->_bf = 0;
        prev->_bf = -1;
    }
    else {
        assert(false);
    }

}

到这里我们就可以把插入函数给补全了！

完整代码可以到我的代码仓库里面看哦！【Gitee】

还是刚刚的测试用例，这一次我们可以看到，它已经没有报错了！

2.3 AVL树的搜索

本质上AVL树还是一个平衡二叉树，所以搜索肯定是少不了的！

它的搜索和KVL树完全一致，利用key来进行搜索，定位value。

所以，我们可以直接搬过来用。

//因为kvl树我们需要修改value，所以返回节点的指针
Node* _FindR(Node* root, const K& key)
{
    if (root == nullptr)
        return nullptr;

    if (root->_kv.first < key)
    {
        return _FindR(root->_right, key);
    }
    else if (root->_kv.first > key)
    {
        return _FindR(root->_left, key);
    }
    else
    {
        return root;//返回节点的指针
    }
}

上面的这个函数我们定义为私有，在公有里面定义一个下面的函数

//查找是通过key来进行的
Node* FindR(const K& key)
{
    return _FindR(_root, key);
}

测试一下可以看到，打印了全0的地址值，即nullptr，说明没有找到34

2.4 如何判断是否符合AVL树的性质

如果每一次我们都要用调试去看当前的代码是否符合二叉树的性质，未免有些太麻烦了

下面我们有两种办法来简洁地判断！

2.4.1 层序遍历（OJ题）

下面的代码是一道OJ题的答案，其要求是让我们把树每一层的节点都插入一个vector，最后返回的是一个嵌套的vector<vector<int>>

来自 https://leetcode.cn/problems/binary-tree-level-order-traversal/

因为我们当前测试的用例都是int类型，所以这里就没有用模板参数。实际上我们应该改成key的类型

vector<vector<int>> levelOrder() 
{
    vector<vector<int>> vv;
    if (_root == nullptr)
        return vv;

    queue<Node*> q;
    int levelSize = 1;
    q.push(_root);

    while (!q.empty())
    {
        // levelSize控制一层一层出
        vector<int> levelV;
        while (levelSize--)
        {
            Node* front = q.front();
            q.pop();
            levelV.push_back(front->_kv.first);
            if (front->_left)
                q.push(front->_left);

            if (front->_right)
                q.push(front->_right);
        }
        vv.push_back(levelV);
        for (auto e : levelV)
        {
            cout << e << " ";
        }
        cout << endl;

        // 上一层出完，下一层就都进队列
        levelSize = q.size();
    }

    return vv;
}

测试一下，可以看到每一层的结果，符合我们AVL树的性质

2.4.2 检查平衡因子

这里我们用两个递归函数，通过计算子树的高度，来判断是否满足AVL树的性质。

只要两个子树的高度差大于1，就说明不是AVL树

//计算高度
int _Height(Node* root)
{
    if (root == nullptr)
        return 0;

    int lh = _Height(root->_left);
    int rh = _Height(root->_right);
    //如果左子树高于右子树，就返回左子树+1（根）
    return lh > rh ? lh + 1 : rh + 1;
}
//判断是否为平衡二叉树
bool _IsBalanceTree(Node* root)
{
    // 空树也是AVL树
    if (nullptr == root)
        return true;

    // 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;

    // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
    // pRoot平衡因子的绝对值超过1，则一定不是AVL树
    if (abs(diff) >= 2)
    {
        cout << root->_kv.first << "节点平衡因子异常" << endl;
        return false;
    }

    if (diff != root->_bf)
    {
        cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
        return false;
    }

    // pRoot的左和右如果都是AVL树，则该树一定是AVL树
    return _IsBalanceTree(root->_left)
        && _IsBalanceTree(root->_right);
}

2.5 利用随机值和顺序值进行测试

下面我们分别利用随机值和顺序值测试AVL树的正确性

void TestAVLTree2()
{
    const size_t N = 1024*1024;
    vector<int> v;
    v.reserve(N);
    srand(time(0));//使用随机数
    for (size_t i = 0; i < N; ++i)
    {
        v.push_back(rand());
        //v.push_back(i);
    }

    AVLTree<int, int> t;
    for (auto e : v)
    {
        t.Insert(make_pair(e, e));
    }

    cout << "是否平衡?" << t.IsBalanceTree() << endl;
    cout << "高度:" << t.Height() << endl;
}