在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn）。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 ——Wiki

1. 为什么要有平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

为了避免这种“退化”，改善查找效率，就可以使用平衡二叉树。

2. 定义

平衡二叉查找树：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

  1. 可以是空树。
  2. 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

平衡之意，如天平，即两边的分量大约相同。

3. 平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

二叉树的深度

我最开始没理解平衡因子就是理解错了这个深度。深度的定义如下：

根节点到这个节点所经历的边的个数。

记不住的话可以想象生活中的例子。比如水中的深度，一般是从上往下计量的。所以深度是从上向下的。
(图示后面再补吧QAQ)

4. AVL树插入的失衡与调整

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

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

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

4.1 左旋

对节点进行左旋操作，流程如下：

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

代码实现

/*****************************************************************
Function:LeftRotate
Description：左旋。
*****************************************************************/

Node* AVL::LeftRotate(Node * node)
{
    Node* parent = node->parent;
    Node* left_child = node->left;
    Node* right_child = node->right;

    //判断右节点的左孩子
    if (right_child->left != nullptr)
        right_child->left->parent = node;

    //改变node的右孩子
    node->right = right_child->left;

    update_depth(node);//更新node节点的深度

    //将node和right_child接在一起
    right_child->left = node;
    node->parent = right_child;

    update_depth(right_child);//更新right_child节点深度

    //如果父节点存在，修改父节点的关系
    if (parent != nullptr)
    {
        if (parent->left == node)
            parent->left = right_child;
        else
            parent->right = right_child;
    }

    right_child->parent = parent;//更新right_child的父亲

    update_depth(right_child);//更新右节点深度

    return right_child;
}

4.2 右旋

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

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

代码实现

/*****************************************************************
Function:RightRotate
Description：右旋。
*****************************************************************/

Node* AVL::RightRotate(Node * node)
{
    Node* parent = node->parent;
    Node* left_child = node->left;
    Node* right_child = node->right;

    //判断左节点的右孩子
    if (left_child->right != nullptr)
        left_child->right->parent = node;

    //改变node的左孩子
    node->left = left_child->right;

    update_depth(node);//更新深度

    //将node和left_child接在一起
    node->parent = left_child;
    left_child->parent = parent;

    //如果父节点存在，修改父节点的关系
    if (parent != nullptr)
    {
        if (parent->left = node)
            parent->left = left_child;
        else
            parent->right = left_child;
    }

    left_child->parent = parent;//更新父节点

    update_depth(left_child);

    return left_child;
}

5. AVL树的插入

5.1 AVL树的四种插入节点方式

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

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

5.2 插入代码实现

/*****************************************************************
Function:insert
Description：插入一个节点。
*****************************************************************/

inline Node* AVL::__insert(Node * node, int data)
{
    if (node == nullptr)
        return new Node(data);

    //根据值的大小递归判断插入位置
    if (data > node->value)
        __insert(node->right, data);
    else if (data < node->value)
        __insert(node->left, data);
    else //如果有重复的就返回当前节点
        return node;

    update_depth(node);//更新当前节点深度

    int factor = balance_factors(node);//平衡因子

    if (factor > 1 && data < node->left->value)
        return RightRotate(node);//LL型最小失衡树
    else if (factor < -1 && data > node->right->value)
        return LeftRotate(node);//RR型最小失衡树
    else if (factor > 1 && data > node->left->value)
    {//LR型最小失衡树
        LeftRotate(node->left);
        return RightRotate(node);
    }
    else if (factor < -1 && data < node->right->value)
    {//RL型最小失衡树
        RightRotate(node->right);
        return LeftRotate(node);
    }

    return node;
}

inline bool AVL::insert(int data)
{
    if (find(data) != nullptr)
        return false;

    __insert(root, data);
    SIZE++;

    return true;
}

5.3 一些总结

  • 在所有的不平衡情况中，都是按照先 寻找最小不平衡树，然后 寻找所属的不平衡类别，再 根据 4 种类别进行固定化程序的操作。
  • LL , LR ，RR ，RL其实已经为我们提供了最后哪个节点作为新的根指明了方向。如 LR 型最后的根节点为原来的根的左孩子的右孩子，RL 型最后的根节点为原来的根的右孩子的左孩子。只要记住这四种情况，可以很快地推导出所有的情况。
  • 维护平衡二叉树，最麻烦的地方在于平衡因子的维护。可以自己动手画一遍加深印象。

6.AVL树的删除

一般的二叉树删除有三种情况：

  1. 删除的节点为叶节点；
  2. 删除的节点仅有一颗子树；
  3. 删除的节点有两颗子树；

AVL树也是一颗二叉搜索树，只是多了一个平衡性质。所以AVL树的删除和二叉搜索树差不多，但是因为其平衡性质需要进行平衡处理。

删除代码实现

/*****************************************************************
Function:erase
Description：删除一个节点。
*****************************************************************/

inline Node * AVL::__erase(Node * node, int data)
{
    if (node == nullptr)
        return node;

    //递归找到需删除的节点
    if (data < node->value)
        __erase(node->left, data);
    else if (data > node->value)
        __erase(node->right, data);
    else
    {
        if (node->left == nullptr || node->right == nullptr)
        {//node为叶节点或node仅有一个孩子
            Node* son = node->left == nullptr ? node->right : node->left;

            //处理node的父节点
            if (node->parent->left == node)
                node->parent->left = son;
            else
                node->parent->right = son;

            if (son != nullptr)//如果有儿子则修改
                son->parent = node->parent;

            delete node;//直接删除node
            return son;
        }
        else //有两个儿子的时候
        {//这里使用前驱或者后继都可以。我使用的是后继
            node->value = find_successor(node)->value;

            //因为使用的是后继所以从右儿子继续
            __erase(node->right, node->value);
        }
    }

    /*以下操作是为了恢复AVL树的平衡性*/
    
    if (node == nullptr)
        return node;

    int factor = balance_factors(node);

    //这两个用 >= 是为了保证一次旋转就可以平衡
    if (factor > 1 && balance_factors(node->left) >= 0)
        return RightRotate(node);//LL型最小失衡树
    else if (factor < -1 && balance_factors(node->right) <= 0)
        return LeftRotate(node);//RR型最小失衡树
    else if (factor > 1 && balance_factors(node->left) < 0)
    {//LR型最小失衡树
        LeftRotate(node->left);
        return RightRotate(node);
    }
    else if (factor < -1 && balance_factors(node->right) < 0)
    {//RL型最小失衡树
        RightRotate(node->right);
        return LeftRotate(node);
    }

    return node;
}

inline Node* AVL::erase(int data)
{
    Node* tmp = find(data);

    if (tmp == nullptr)
        return false;

    SIZE--;

    return __erase(root, data);
}

inline Node* AVL::erase(Node * node)
{
    if (node == nullptr)
        return nullptr;

    SIZE--;

    return __erase(root, node->value);
}

7. 整体代码

这是我在学习时写的代码，我还没有测试，如果发现了BUG请在评论区留言或和我私聊。欢迎指教。

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node
{
    int depth;//树的深度
    int value;

    Node* parent = nullptr;
    Node* left = nullptr;
    Node* right = nullptr;

    Node() :depth(0), value(0) {    }
    Node(int n) :depth(0), value(n) {    }

    void clear()
    {
        depth = value = 0;
        parent = nullptr;
        left = right = nullptr;
    }
};

class AVL
{
private:
    Node* root;
    int SIZE;

private:
    /*左旋，右旋*/
    Node* LeftRotate(Node* node);
    Node* RightRotate(Node* node);

    /*插入, 删除*/
    Node* __insert(Node* node, int data);
    Node* __erase(Node* node, int data);

    /*三序遍历*/
    void __preorderTraversal(Node* node, vector<int> &res);
    void __inorderTraversal(Node* node, vector<int> &res);
    void __postorderTraversal(Node* node, vector<int> &res);

    /*一些辅助函数*/
    int balance_factors(Node* node);//获取平衡因子
    void update_depth(Node* node);//更新当前节点深度

public:
    /*构造，析构*/
    AVL() :SIZE(0) {    }
    AVL(vector<int> data);
    ~AVL();

    /*插入*/
    bool insert(int data);

    /*删除*/
    Node* erase(int data);
    Node* erase(Node* node);
    void clear();

    /*查找*/
    Node* find(int data);

    /*寻找前驱, 后继*/
    Node* find_predecesser(Node* node);
    Node* find_successor(Node* node);

    /*树信息*/
    int size() { return SIZE; }
    int depth(Node* node) { return node == nullptr ? 0 : node->depth; }
    bool empty() { return SIZE == 0; }
    Node* begin() { return root; }

    /*三序遍历*/
    vector<int> preorderTraversal(Node* node);
    vector<int> inorderTraversal(Node* node);
    vector<int> postorderTraversal(Node* node);
};

/*****************************************************************
Function:AVL
Description：构造函数，将data里面的数据输入到树中。
*****************************************************************/

AVL::AVL(vector<int> data)
{
    for (auto n : data)//C++11支持的冒号遍历
        insert(n);  //auto的作用是自动选择相应的类型

    return;
}

/*****************************************************************
Function:~AVL
Description：析构函数。
*****************************************************************/

AVL::~AVL()
{
    clear();
    delete root;

    return;
}

/*****************************************************************
Function:LeftRotate
Description：左旋。
*****************************************************************/

inline Node* AVL::LeftRotate(Node * node)
{
    Node* parent = node->parent;
    Node* left_child = node->left;
    Node* right_child = node->right;

    //判断右节点的左孩子
    if (right_child->left != nullptr)
        right_child->left->parent = node;

    //改变node的右孩子
    node->right = right_child->left;

    update_depth(node);//更新node节点的深度

    //将node和right_child接在一起
    right_child->left = node;
    node->parent = right_child;

    update_depth(right_child);//更新right_child节点深度

    //如果父节点存在，修改父节点的关系
    if (parent != nullptr)
    {
        if (parent->left == node)
            parent->left = right_child;
        else
            parent->right = right_child;
    }

    right_child->parent = parent;//更新right_child的父亲

    update_depth(right_child);//更新右节点深度

    return right_child;
}

/*****************************************************************
Function:RightRotate
Description：右旋。
*****************************************************************/

inline Node* AVL::RightRotate(Node * node)
{
    Node* parent = node->parent;
    Node* left_child = node->left;
    Node* right_child = node->right;

    //判断左节点的右孩子
    if (left_child->right != nullptr)
        left_child->right->parent = node;

    //改变node的左孩子
    node->left = left_child->right;

    update_depth(node);//更新深度

    //将node和left_child接在一起
    node->parent = left_child;
    left_child->parent = parent;

    //如果父节点存在，修改父节点的关系
    if (parent != nullptr)
    {
        if (parent->left = node)
            parent->left = left_child;
        else
            parent->right = left_child;
    }

    left_child->parent = parent;//更新父节点

    update_depth(left_child);

    return left_child;
}

/*****************************************************************
Function:insert
Description：插入一个节点。
*****************************************************************/

inline Node* AVL::__insert(Node * node, int data)
{
    if (node == nullptr)
        return new Node(data);

    //根据值的大小递归判断插入位置
    if (data > node->value)
        __insert(node->right, data);
    else if (data < node->value)
        __insert(node->left, data);
    else //如果有重复的就返回当前节点
        return node;

    update_depth(node);//更新当前节点深度

    int factor = balance_factors(node);//平衡因子

    if (factor > 1 && data < node->left->value)
        return RightRotate(node);//LL型最小失衡树
    else if (factor < -1 && data > node->right->value)
        return LeftRotate(node);//RR型最小失衡树
    else if (factor > 1 && data > node->left->value)
    {//LR型最小失衡树
        LeftRotate(node->left);
        return RightRotate(node);
    }
    else if (factor < -1 && data < node->right->value)
    {//RL型最小失衡树
        RightRotate(node->right);
        return LeftRotate(node);
    }

    return node;
}

inline bool AVL::insert(int data)
{
    if (find(data) != nullptr)
        return false;

    __insert(root, data);
    SIZE++;

    return true;
}

/*****************************************************************
Function:erase
Description：删除一个节点。
*****************************************************************/

inline Node * AVL::__erase(Node * node, int data)
{
    if (node == nullptr)
        return node;

    //递归找到需删除的节点
    if (data < node->value)
        __erase(node->left, data);
    else if (data > node->value)
        __erase(node->right, data);
    else
    {
        if (node->left == nullptr || node->right == nullptr)
        {//node为叶节点或node仅有一个孩子
            Node* son = node->left == nullptr ? node->right : node->left;

            //处理node的父节点
            if (node->parent->left == node)
                node->parent->left = son;
            else
                node->parent->right = son;

            if (son != nullptr)//如果有儿子则修改
                son->parent = node->parent;

            delete node;//直接删除node
            return son;
        }
        else //有两个儿子的时候
        {//这里使用前驱或者后继都可以。我使用的是后继
            node->value = find_successor(node)->value;

            //因为使用的是后继所以从右儿子继续
            __erase(node->right, node->value);
        }
    }

    /*以下操作是为了恢复AVL树的平衡性*/
    
    if (node == nullptr)
        return node;

    int factor = balance_factors(node);

    //这两个用 >= 是为了保证一次旋转就可以平衡
    if (factor > 1 && balance_factors(node->left) >= 0)
        return RightRotate(node);//LL型最小失衡树
    else if (factor < -1 && balance_factors(node->right) <= 0)
        return LeftRotate(node);//RR型最小失衡树
    else if (factor > 1 && balance_factors(node->left) < 0)
    {//LR型最小失衡树
        LeftRotate(node->left);
        return RightRotate(node);
    }
    else if (factor < -1 && balance_factors(node->right) < 0)
    {//RL型最小失衡树
        RightRotate(node->right);
        return LeftRotate(node);
    }

    return node;
}

inline Node* AVL::erase(int data)
{
    Node* tmp = find(data);

    if (tmp == nullptr)
        return false;

    SIZE--;

    return __erase(root, data);
}

inline Node* AVL::erase(Node * node)
{
    if (node == nullptr)
        return nullptr;

    SIZE--;

    return __erase(root, node->value);
}

/*****************************************************************
Function:clear
Description：清空树。
*****************************************************************/

inline void AVL::clear()
{//利用了广搜的思想遍历删除
    if (root == nullptr)
        return;

    queue<Node*> q;

    q.push(root);

    while (!q.empty())
    {
        Node* tmp = q.front();
        q.pop();

        if (tmp->left != nullptr)
            q.push(tmp->left);

        if (tmp->right != nullptr)
            q.push(tmp->right);

        delete tmp;

        SIZE--;
    }

    root->clear();

    return;
}

/*****************************************************************
Function:find
Description：查找值为data的节点。
*****************************************************************/

inline Node * AVL::find(int data)
{//二分搜索
    if (root == nullptr)
        return nullptr;

    Node* tmp = root;

    while (tmp != nullptr)
    {
        if (tmp->value == data)
            return tmp;
        else if (data > tmp->value)
            tmp = tmp->right;
        else if (data < tmp->value)
            tmp = tmp->left;
    }

    return nullptr;
}

/*****************************************************************
Function:find_predecessor
Description：查找节点的前驱。

节点x的前驱，就是指value小于x节点中value最大的那个节点
若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点
如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里
没有x节点的祖先。
*****************************************************************/

inline Node * AVL::find_predecesser(Node * node)
{
    if (node == nullptr)
        return nullptr;

    Node* tmp = node;

    if (node->left != nullptr)
    {
        tmp = node->left;

        while (tmp->right != nullptr)
            tmp = tmp->right;

        return tmp;
    }

    while (tmp->parent != nullptr && tmp->parent->left != tmp)
        tmp = tmp->parent;

    return tmp->parent;
}

/*****************************************************************
Function:find_predecessor
Description：查找节点的后继。

节点x的后继，就是指value大于x节点中value最小的那个节点
若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点
如果x的右子树为空，那么我们就要向上找x的第一个有左孩子且右子树里
没有x节点的祖先。
*****************************************************************/

inline Node * AVL::find_successor(Node * node)
{
    if (node == nullptr)
        return nullptr;

    Node* tmp = node;

    if (node->right != nullptr)
    {
        tmp = node->right;

        while (tmp->left != nullptr)
            tmp = tmp->left;

        return tmp;
    }

    while (tmp->parent != nullptr && tmp->parent->right != tmp)
        tmp = tmp->parent;

    return tmp->parent;
}

/*****************************************************************
Function:balance_factors
Description：获取当前节点的平衡因子。
*****************************************************************/

inline int AVL::balance_factors(Node * node)
{
    if (node == nullptr)
        return 0;

    return depth(node->left) - depth(node->right);
}

/*****************************************************************
Function:update_depth
Description：更新当前节点深度，为旋转做准备。
*****************************************************************/

inline void AVL::update_depth(Node * node)
{
    if (node == nullptr)
        return;

    if (node->left == nullptr && node->right == nullptr)
        node->depth = 0;//叶节点的深度为0
    else
        node->depth = max(depth(node->left), depth(node->right)) + 1;

    return;
}

/*****************************************************************
Function:preorderTraversal
Description：前序遍历。
*****************************************************************/

inline void AVL::__preorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        res.push_back(node->value);
        __preorderTraversal(node->left, res);
        __preorderTraversal(node->right, res);
    }

    return;
}

inline vector<int> AVL::preorderTraversal(Node* node)
{
    vector<int> res;
    __preorderTraversal(node, res);
    return res;
}

/*****************************************************************
Function:inorderTraversal
Description：中序遍历。
*****************************************************************/

inline void AVL::__inorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        __inorderTraversal(node->left, res);
        res.push_back(node->value);
        __inorderTraversal(node->right, res);
    }

    return;
}

inline vector<int> AVL::inorderTraversal(Node* node)
{
    vector<int> res;
    __inorderTraversal(node, res);
    return res;
}

/*****************************************************************
Function:postorderTraversal
Description：后序遍历。
*****************************************************************/

inline void AVL::__postorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        __postorderTraversal(node->left, res);
        __postorderTraversal(node->right, res);
        res.push_back(node->value);
    }

    return;
}

inline vector<int> AVL::postorderTraversal(Node* node)
{
    vector<int> res;
    __postorderTraversal(node, res);
    return res;
}

8.随便写写

这个平衡二叉树花了我两三天才算是比较弄懂它的实现方法。这里有个小插曲，那个插入和删除的参考代码，我写完后才发现是JAVA的(捂脸)。在写的时候也踩了许多坑。我想了很多不可能出现的情况，然后就写不下去了，到最后才发现根本不存在这些问题。到最后想想还是不够仔细啊。

最后修改：2019 年 07 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏