目录

一、AVL 树的概念

二、AVL 树节点的定义

三、AVL 树的插入

四、AVL 树的平衡调整

五、AVL 树的删除

六、AVL 树的实现

6.1 - AVL.h

6.2 - test.cpp

 

一、AVL 树的概念

二叉搜索树查找算法的性能取决于二叉树搜索树的形状，而二叉搜索树的形状则取决于数据集。如果数据呈有序排列，则二叉搜索树为单支树，查找的时间复杂度为 O(n)；反之，如果二叉搜索树的形状合理，则查找速度较快，查找的时间复杂度为 O(log_2^n)。事实上，树的高度越小，查找速度越快，因此，希望二叉树的高度尽可能小。下面将讨论一种特殊类型的二叉搜索树，称为平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree），因由前苏联数学家 Adelson-Velskii 和 Landis 提出，所以又称 AVL 树。

平衡二叉树或者是空树，或者是具有如下特征的二叉搜索树：

  1. 左子树和右子树的高度之差的绝对值不超过 1。

  2. 左子树和右子树也是平衡二叉树。

若将二叉树上节点的平衡因子（BF, Balance Factor）定义为该节点左子树和右子树的高度之差，则平衡二叉树上的所有节点的平衡因子只可能是 -1、0 和 1。只要二叉树上有一个节点的平衡因子的绝对值大于 1，则该二叉树就是不平衡。

例如，下面图 (a) 所示为两棵平衡二叉树，图 (b) 所示则为两棵不平衡的二叉树，节点中的值为该结点的平衡因子。

因为 AVL 树上任何节点的左右子树的高度之差都不超过 1，则可以证明它的深度和 log_2^n 是同数量级的（其中 n 为节点个数）。由此，其查找的时间复杂度是 O(log_2^n)。

二、AVL 树节点的定义

template<class K, class V>
struct AVLNode
{
    AVLNode<K, V>* _left;
    AVLNode<K, V>* _right;
    AVLNode<K, V>* _parent;
    std::pair<K, V> _kv;
    int _bf;
​
    AVLNode(const std::pair<K, V>& kv = std::pair<K, V>())
        : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0)
    { } 
};

三、AVL 树的插入

当新增的节点 *cur（指向节点的指针为 cur） 插入到其双亲节点 *parent（指向节点的指针为 parent）的左边时，双亲节点的平衡因子 +1；反之，当新增的节点插入到其双亲节点的右边时，双亲节点的平衡因子 -1。

  1. 若双亲节点的平衡因子原来为 -1 或者 1，在它的左边或者右边插入新增的节点后，它的平衡因子变为 0。由于以 *parent 为根节点的子树的高度没有发生变化，因此也不会影响除 *parent 以外的其它祖先节点的平衡因子，插入完成。

  2. 若双亲节点的平衡因子原来为 0，在它的左边或者右边插入新增的节点后，它的平衡因子变为 1 或者 -1。由于以 *parent 为根节点的子树的高度增高了 1，此时也就会影响其它祖先节点的平衡因子，需要往上更新。

    往上更新其它祖先节点的平衡因子的方式和一开始插入新增节点 *cur 时更新其双亲节点 *parent 的平衡因子的方式是一样的，即如果 *cur 在祖先节点的左子树中，则祖先节点的平衡因子 +1；如果 *cur 在祖先节点的右子树中，则祖先节点的平衡因子 -1。

    • 如果祖先节点的平衡因子被更新为 0，则说明更新完成了，也意味着插入完成了。

    • 如果祖先节点的平衡因子被更新为 1 或者 -1，则说明还需要继续往上更新，直到某个祖先节点的平衡因子被更新为 0，或者直到更新完根节点，当根节点的平衡因子被更新为 0、1 或者 -1 时，意味着更新和插入也都完成了。

    • 如果祖先节点的平衡因子被更新为 2 或者 -2（即其较高的子树增高了），就需要对以该节点为根节点的子树（称为最小不平衡子树）做平衡调整来恢复平衡。

四、AVL 树的平衡调整

假设最小不平衡子树的根节点为 A，则失去平衡后进行调整的规律可归纳为下列 4 种情况。

  1. LL 型：由于在 A 左子树根节点的左子树上插入节点，A 的平衡因子由 1 增至 2，致使以 A 为根节点的子树失去平衡，则需进行一次向右的顺时针旋转操作。

    void LL(Node* pA)
{
    Node* pB = pA->_left;
    Node* pBR = pB->_right;
​
    pA->_left = pBR;
    if (pBR)
        pBR->_parent = pA;
​
    pB->_right = pA;
    Node* tmp = pA->_parent;
    pA->_parent = pB;
    pB->_parent = tmp;
​
    if (tmp == nullptr)  // 或者 _root == pA
    {
        _root = pB;
    }
    else
    {
        if (tmp->_left == pA)
            tmp->_left = pB;
        else
            tmp->_right = pB;
    }
​
    pA->_bf = pB->_bf = 0;
}

  2. RR 型：由于在 A 的右子树根节点的右子树上插入节点，A 的平衡因子由 -1 变成 -2，致使以 A 为根节点的子树失去平衡，则需进行一次向左的逆时针旋转操作。

    void RR(Node* pA)
{
    Node* pB = pA->_right;
    Node* pBL = pB->_left;
​
    pA->_right = pBL;
    if (pBL)
        pBL->_parent = pA;
​
    pB->_left = pA;
    Node* tmp = pA->_parent;
    pA->_parent = pB;
    pB->_parent = tmp;
​
    if (tmp == nullptr)  // 或者 _root == pA
    {
        _root = pB;
    }
    else
    {
        if (tmp->_left == pA)
            tmp->_left = pB;
        else
            tmp->_right = pB;
    }
​
    pA->_bf = pB->_bf = 0;
}

  3. LR 型：由于在 A 的左子树的根节点的右子树上插入节点，A 的平衡因子由 1 增至 2，致使以 A 为根节点的子树失去平衡，则需要进行两次旋转操作。

    void LR(Node* pA)
{
    Node* pB = pA->_left;
    Node* pC = pB->_right;
    int bf = pC->_bf;
​
    RR(pB);
    LL(pA);
​
    if (bf == 0)  // LR（0）型
    {
        pA->_bf = 0;
        pB->_bf = 0;
        pC->_bf = 0;
    }
    else if (bf == 1)  // LR（L）型
    {
        pA->_bf = -1;
        pB->_bf = 0;
        pC->_bf = 0;
    }
    else if (bf == -1)  // LR（R）型
    {
        pA->_bf = 0;
        pB->_bf = 1;
        pC->_bf = 0;
    }
}

  4. RL 型：由于在 A 的右子树根节点的左子树上插入节点，A 的平衡因子由 -1 变为 -2，致使以 A 为根节点的子树失去平衡，则旋转方法和 LR 型对称，也需进行两次旋转，先顺时针右旋，再逆时针左旋。

    void RL(Node* pA)
{
    Node* pB = pA->_right;
    Node* pC = pB->_left;
    int bf = pC->_bf;
​
    LL(pB);
    RR(pA);
​
    if (bf == 0)  // RL（0）型
    {
        pA->_bf = 0;
        pB->_bf = 0;
        pC->_bf = 0;
    }
    else if (bf == 1)  // RL（L）型
    {
        pA->_bf = 0;
        pB->_bf = -1;
        pC->_bf = 0;
    }
    else if (bf == -1)  // RL（R）型
    {
        pA->_bf = 1;
        pB->_bf = 0;
        pC->_bf = 0;
    }
}

总结：无论哪一种情况，在经过平衡旋转处理之后，以 B 或 C 为根的新子树为平衡二叉树，而且它们的高度和插入之前以 A 为根的子树相同。因此，当平衡的二叉搜索树因插入节点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。

五、AVL 树的删除

AVL 树的删除算法与二叉搜索树类似，不同之处在于：若删除后破坏了 AVL 树的高度平衡性质，还需要做平衡化旋转。

  1. 如果被删节点 *cur 的左、右子树都不为空。首先找到左子树中键值最大的节点 *leftMax（或者找到右子树中键值最小的节点 *rightMin），然后进行交换，即 std::swap(cur->_kv, leftMax->_kv);， 此时被删节点就变成了 *leftMax，该节点的右子树一定为空。

  2. 如果被删节点 *cur 最多只有一个孩子 *child。可以把 *cur 的双亲节点 *parent 中原来指向 *cur 的指针改为指向 *child。如果 *cur 没有孩子，则 *parent 的相应指针置为 nullptr。由于以 *parent 为根节点的子树的高度缩短了 1，所以需沿着 *parent 通向根节点的路径，往上追踪高度的这一变化对路径上各个节点的影响。

考查 *cur 的祖先节点，若 *cur 在祖先节点的左子树中，则祖先节点的平衡因子 -1，反之，则祖先节点的平衡因子 +1。根据祖先节点更新后的平衡因子，按以下三种情况分别进行处理：

  1. 祖先节点的平衡因子原来为 0，在它的左子树或者右子树被缩短后，它的平衡因子变为 -1 或者 1。由于以该节点为根的子树的高度没有改变，则不需要往上更新了，删除结束。

  2. 祖先节点的平衡因子原来为 1 或者 -1，在它的较高的子树被缩短后，它的平衡因子改为 0。此时以该节点为根的子树平衡，但其高度减 1，所以需要继续往上更新。

  3. 祖先节点的平衡因子原来为 -1 或者 1，在它的较矮的子树被缩短后，它的平衡因子变为 -2 或者 2。此时以该节点为根的子树不平衡，需要进行平衡化旋转来恢复平衡。

    根据祖先节点较高的子树的根（该子树未被缩短）的平衡因子，有如下 3 种平衡化操作：

    (1) 如果祖先节点较高的子树的根的平衡因子为 0，则执行一个单旋转来恢复子树的平衡。

    由于旋转平衡后以 *q 为根节点的子树的高度没有发生改变，所以不需要再往上更新了，删除结束。

    (2) 如果祖先节点较高的子树的根的平衡因子和祖先节点的平衡因子的正负号相同，则执行一个单旋转来恢复平衡。

    由于经过旋转平衡旋转后以 *q 为根节点的子树的高度降低了 1，所以需要继续往上更新。

    (3) 如果祖先节点较高的子树的根的平衡因子和祖先节点的平衡因子的正负号相反，则执行一个双旋转来恢复平衡。

    由于经过平衡化处理后以 *r 为根的子树的高度降低了 1，所以还需要继续往上更新。

六、AVL 树的实现

6.1 - AVL.h

#pragma once
​
#include <utility>
​
template<class K, class V>
struct AVLNode
{
    AVLNode<K, V>* _left;
    AVLNode<K, V>* _right;
    AVLNode<K, V>* _parent;
    std::pair<K, V> _kv;
    int _bf;
​
    AVLNode(const std::pair<K, V>& kv = std::pair<K, V>())
        : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0)
    { } 
};
​
template<class K, class V>
class AVL
{
    typedef AVLNode<K, V> Node;
public:
    AVL() : _root(nullptr) { }
​
    ~AVL()
    {
        Destroy(_root);
    }
​
    bool isBalanced() const
    {
        return _isBalanced(_root);
    }
​
    bool insert(const std::pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
​
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            parent = cur;
            if (kv.first < cur->_kv.first)
                cur = cur->_left;
            else if (kv.first > cur->_kv.first)
                cur = cur->_right;
            else
                return false;
        }
​
        cur = new Node(kv);
        if (kv.first < parent->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;
        cur->_parent = parent;  // 注意：这一步很容易被忽略
​
        // 往上更新 *cur 的祖先节点的平衡因子
        while (parent)
        {
            if (parent->_left == 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 && cur->_bf == 1)
                    LL(parent);
                else if (parent->_bf == -2 && cur->_bf == -1)
                    RR(parent);
                else if (parent->_bf == 2 && cur->_bf == -1)
                    LR(parent);
                else if (parent->_bf == -2 && cur->_bf == 1)
                    RL(parent);
                // 跳出循环
                break;
            }
        }
        return true;
    }
​
    bool erase(const std::pair<K, V>& kv)
    {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (kv.first == cur->_kv.first)
                break;
​
            parent = cur;
            if (kv.first < cur->_kv.first)
                cur = cur->_left;
            else
                cur = cur->_right;
        }
​
        if (cur == nullptr)  // 树为空或者在树中未找到被删节点
            return false;
​
        // 被删节点的左、右子树都不为空
        if (cur->_left && cur->_right)
        {
            parent = cur;
            Node* leftMax = cur->_left;
            while (leftMax->_right)
            {
                parent = leftMax;
                leftMax = leftMax->_right;
            }
            std::swap(cur->_kv, leftMax->_kv);
            cur = leftMax;  
            // 此时被删节点就变成了 *leftMax，该节点的右子树为空
        }
​
        // 被删节点最多只有一个孩子
        Node* child;
        if (cur->_left)
            child = cur->_left;
        else
            child = cur->_right;
​
        if (parent == nullptr)  // 被删节点为根节点
        {
            _root = child;  
        }
        else
        {
            if (parent->_left == cur)
            {
                --parent->_bf;
                parent->_left = child;
            }
            else
            {
                ++parent->_bf;
                parent->_right = child;
            }
​
            // 往上更新 *cur 的祖先节点的平衡因子
            bool isFirst = true;
            while (parent)
            {
                // 注意：在第一次循环中，child 可能为 nullptr，
                // 不能通过下面的方式判断 *cur 在其祖先节点的左子树中，还是右子树中，
                // 所以需要在循环外更新 *cur 的双亲节点的平衡因子，
                // 在循环内更新 *cur 其它祖先节点的平衡因子。
                if (isFirst == false)
                {
                    if (parent->_left == child)
                        --parent->_bf;
                    else
                        ++parent->_bf;
                }
                isFirst = false;
​
                if (parent->_bf == -1 || parent->_bf == 1)
                {
                    break;
                }
                else if (parent->_bf == -2 || parent->_bf == 2)
                {
                    int sign = 0;  // 祖先节点的平衡因子的正负号
                    Node* higher;
                    if (parent->_bf < 0)
                    {
                        sign = -1;
                        higher = parent->_right;
                    }
                    else
                    {
                        sign = 1;
                        higher = parent->_left;
                    }
​
                    if (higher->_bf == 0)
                    {
                        if (sign < 0)
                        {
                            RR(parent);
                            parent->_bf = -1;
                            higher->_bf = 1;
                        }
                        else
                        {
                            LL(parent);
                            parent->_bf = 1;
                            higher->_bf = -1;
                        }
                        break;  // 不需要继续往上更新，跳出循环
                    }
                    else if (higher->_bf == sign)  // 两节点的平衡因子同号
                    {
                        if (sign < 0)
                        {
                            RR(parent);
                            parent = higher;
                            child = parent->_left;
                        }
                        else
                        {
                            LL(parent);
                            parent = higher;
                            child = parent->_right;
                        }
                    }
                    else  // 两节点的平衡因子反号
                    {
                        if (sign < 0)
                        {
                            Node* tmp = parent->_right->_left;
                            RL(parent);
                            parent = tmp;
                            child = parent->_left;
                        }
                        else
                        {
                            Node* tmp = parent->_left->_right;
                            LR(parent);
                            parent = tmp;
                            child = parent->_right;
                        }
                    }
                }
                // 继续往上更新
                child = parent;
                parent = parent->_parent;
            }
        }
        delete cur;
        return true;
    }
private:
    void Destroy(Node*& root)
    {
        //【注意:root 为 _root 或者某个节点的左或右作指针的引用】
        if (root == nullptr)
            return;
​
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
        root = nullptr;
    }
​
    int Height(Node* root) const
    {
        if (root == nullptr)
            return 0;
​
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
​
    bool _isBalanced(Node* root) const
    {
        if (root == nullptr)
            return true;
​
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        return abs(leftHeight - rightHeight) < 2
            && _isBalanced(root->_left)
            && _isBalanced(root->_right);
    }
​
    void LL(Node* pA)
    {
        Node* pB = pA->_left;
        Node* pBR = pB->_right;
​
        pA->_left = pBR;
        if (pBR)
            pBR->_parent = pA;
​
        pB->_right = pA;
        Node* tmp = pA->_parent;
        pA->_parent = pB;
        pB->_parent = tmp;
​
        if (tmp == nullptr)  // 或者 pA == _root
        {
            _root = pB;
        }
        else
        {
            if (tmp->_left == pA)
                tmp->_left = pB;
            else
                tmp->_right = pB;
        }
​
        pA->_bf = pB->_bf = 0;
    }
​
    void RR(Node* pA)
    {
        Node* pB = pA->_right;
        Node* pBL = pB->_left;
​
        pA->_right = pBL;
        if (pBL)
            pBL->_parent = pA;
​
        pB->_left = pA;
        Node* tmp = pA->_parent;
        pA->_parent = pB;
        pB->_parent = tmp;
​
        if (tmp == nullptr)  // 或者 pA == _root
        {
            _root = pB;
        }
        else
        {
            if (tmp->_left == pA)
                tmp->_left = pB;
            else
                tmp->_right = pB;
        }
​
        pA->_bf = pB->_bf = 0;
    }
​
    void LR(Node* pA)
    {
        Node* pB = pA->_left;
        Node* pC = pB->_right;
        int bf = pC->_bf;
​
        RR(pB);
        LL(pA);
​
        if (bf == 0)  // LR（0）型
        {
            pA->_bf = 0;
            pB->_bf = 0;
            pC->_bf = 0;
        }
        else if (bf == 1)  // LR（L）型
        {
            pA->_bf = -1;
            pB->_bf = 0;
            pC->_bf = 0;
        }
        else if (bf == -1)  // LR（R）型
        {
            pA->_bf = 0;
            pB->_bf = 1;
            pC->_bf = 0;
        }
    }
​
    void RL(Node* pA)
    {
        Node* pB = pA->_right;
        Node* pC = pB->_left;
        int bf = pC->_bf;
​
        LL(pB);
        RR(pA);
​
        if (bf == 0)  // RL（0）型
        {
            pA->_bf = 0;
            pB->_bf = 0;
            pC->_bf = 0;
        }
        else if (bf == 1)  // RL（L）型
        {
            pA->_bf = 0;
            pB->_bf = -1;
            pC->_bf = 0;
        }
        else if (bf == -1)  // RL（R）型
        {
            pA->_bf = 1;
            pB->_bf = 0;
            pC->_bf = 0;
        }
    }
private:
    Node* _root;
};

6.2 - test.cpp

#include "AVL.h"
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
​
void TestAVL1()
{
    // int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };  // ok
    int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    AVL<int, int> t;
    for (const auto& e : arr)
    {
        t.insert(make_pair(e, e));
        if (!t.isBalanced())
        {
            cout << "插入操作有误！" << endl;
            exit(-1);
        }
    }
    cout << "插入完成~" << endl;
​
    for (const auto& e : arr)
    {
        t.erase(make_pair(e, e));
        if (!t.isBalanced())
        {
            cout << "删除操作有误！" << endl;
            exit(-1);
        }
    }
    cout << "删除完成~" << endl;
}
​
void TestAVL2()
{
    srand((unsigned int)time(0));
    size_t N = 1000;
    vector<int> v;
    for (size_t i = 0; i < N; ++i)
    {
        v.push_back(rand());
    }
​
    AVL<int, int> t;
    for (const auto& e : v)
    {
        t.insert(make_pair(e, e));
        if (!t.isBalanced())
        {
            cout << "插入操作有误！" << endl;
            exit(-1);
        }
    }
    cout << "插入完成~" << endl;
​
    for (const auto& e : v)
    {
        t.erase(make_pair(e, e));
        if (!t.isBalanced())
        {
            cout << e << endl;
            cout << "删除操作有误！" << endl;
            exit(-1);
        }
    }
    cout << "删除完成~" << endl;
}
​
int main()
{
    TestAVL1();
    TestAVL2();
    return 0;
}

# c++ # 学习 # java
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊