【C++】AVL树

?write in front?
?所属专栏： C++学习
?️博客主页：睿睿的博客主页
?️代码仓库：?VS2022_C语言仓库
?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

文章目录

• 前言：
• 一.AVL树的概念
• 二.AVL树结点的定义：
• 三.插入结点操作：
• • 1.先根据key的大小将结点插入其应该在的位置
  • 2.更新平衡因子
  • 3.根据平衡因子不同的情况进行不同的操作：
  • • 情况1：父节点的平衡因子等于0
    • 情况2：父节点的平衡因子变成1或-1：
    • 情况3：父节点的平衡因子变成2或-2：
    • • 左单旋：新节点插入较高右子树的右侧—-右右
      • 右单旋：新节点插入较高左子树的左侧—-左左：
      • 先左单旋再右单旋：节点插入较高左子树的右侧—-左右：
      • 先右单旋再左单旋：新节点插入较高右子树的左侧—-右左：
• 四.AVL树的删除(了解)
• 五.AVL树的验证:
• • 1.二叉搜索树的验证：
  • 2.验证其为平衡树：
  • • a.每个节点子树高度差的绝对值不超过1
    • b.节点的平衡因子是否计算正确
• 总结

前言：

  在前面我们学习了二叉搜索树，一个查询效率非常高的一个数据结构，但是如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，效率就变成了log(n)（直接变成链表了）。所以，为了解决这种方法，大佬们创造出了AVL树和红黑树！
  今天我们就来讲解并浅浅的手撕一下AVL树。

一.AVL树的概念

  两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决效率低的方法：

  当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
  简单的说，就是每插入一个结点，就检查一下该结点的左右子树高度差，如果超过1，那就进行调整（也就是旋转，后面会说到）。

所以AVL树的性质如下：

• 空树root=nullptr
• 非空树：
• 它的左右子树都是AVL树
• 左右子树高度之差的绝对值不超过1

二.AVL树结点的定义：

  其实，AVL树就是比我们之前学的二叉搜索树多一个平衡因子和一个父节点：

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

  而父节点是为了解决旋转操作而做的准备。平衡因子_bf，用来表示节点的平衡状态。通常，平衡因子是右子树的高度减去左子树的高度。AVL树要求每个节点的平衡因子在[-1, 1]范围内，以保持树的平衡。

三.插入结点操作：

  AVL树的插入操作分为三个步骤，认真看相信你一定能学会：

1.先根据key的大小将结点插入其应该在的位置

  这里的操作和二叉搜索树一样，就不用多说了：

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
    //空结点直接插入
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
//找到位置
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            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;

2.更新平衡因子

我们对平衡因子的定义是：

右子树的高度-左子树的高度

所以要搞清楚每一个结点的平衡因子，在插入的时候就一定要算好。

• 如果我们插入的结点在父亲结点的右边，那父亲节的的平衡因子是不是就相当于+1了

• 同样的如果我们插入的结点在父亲的左边，那就相当于父亲的平衡因子-1了。

  if (cur == parent->_left)

          {
              parent->_bf--;
          }

  else // if (cur == parent->_right)

          {
              parent->_bf++;
          }

3.根据平衡因子不同的情况进行不同的操作：

情况1：父节点的平衡因子等于0

  更新以后parent平衡因子等于0，说明parent所在子树的高度不变(每次只插入一个结点，高度就要么增加1不平衡，要不就不变），不会影响祖先结点的平衡因子，就不用继续沿着root的路径往上走

情况2：父节点的平衡因子变成1或-1：

  更新以后parent的平衡因子等于1或-1，说明parent的高度变了，也就说明parent所在的子树高度变高了，此时就一定会影响到祖先结点的平衡因子。此时我们就要继续重复第二步骤：更新父亲的父亲的平衡因子，此时只要让cur=parent即可。

//当parent为空的时候就停止更新结点
while (parent)
    {
    //不断更新结点：
        if (cur == parent->_left)
        {
            parent->_bf--;
        }
        else 
        {
                parent->_bf++;
        }
        //情况1：停止更新
        if (parent->_bf == 0)
        {
        // 更新结束
            break;
        }
        //情况2：继续向上更新
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            // 继续往上更新
            cur = parent;
            parent = parent->_parent;
        }
        //情况3：旋转
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            // 子树不平衡了，需要旋转
        }
        }

情况3：父节点的平衡因子变成2或-2：

  更新以后parent为2或-2，说明parent的子树高度变化，并且已经不平衡了，此时就要对于parent进行旋转。

那么什么是旋转呢？

我们以这个图为例子：

此时搜索树的高度已经不平衡了，我们就要对其进行旋转，旋转以后会变成这个样子：

其实细心的大家会发现，旋转之后其实就相当于让parent高的那一侧少了一层结点，让parent低的那层多了一层结点。其实本质就是本来左右差为2，让多的那一边把多的一个拿给少的，此时也就正好平衡了。

那么，旋转到底是怎么操作的呢？

这里我们要先记着旋转的前提：

1. 保持二叉搜索树
2. 变成平衡树并且降低这个子树的高度

在这里呢，旋转有很多种情况，最终分为下面的四种：

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

左单旋的核心操作是这样的：

parent->right=cur->left;
cur->left=parent;

我们先举一个简单的例子：

这个树在通过左单旋之后会变成这样：

其实这里的本质就是：cur是在parent的右边，一定是比parent大的，所以说我们的parent可以放在cur的左边，这是没有问题的，而cur的左边那个结点怎么处理呢？cur左边的那个结点也是比parent大的，但是又要比cur小，所以我们将其放在parent的右边就可以了。这个时候也是满足二叉搜索树的性质，而且让树也平衡了。

当然这里还有特殊情况要判断一下，就是如果cur左边为空，要多判断一下。

具体旋转途径如下：

那么我们何时左单旋呢？显而易见，cur的值为1，parent为2的时候就是左单旋了：

void RotateL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        //这里要将其与上面的树连接起来，而parent的位置会改变，所以我们要提前记录下parent的parent结点。
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
        parent->_bf = cur->_bf = 0;
    }

当然，这里还有一个很重要的就是旋转完以后，cur和parent的平衡因子都变成了0！！原因我刚刚也分析过了。

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

这里和上面的右单旋其实是类似的，我们直接来看看过程图就可以了：

/*
上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左
子树增加
了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子
树增加一层，
即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有
右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点
的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
同学们再此处可举一些详细的例子进行画图，考虑各种情况，加深旋转的理解
*/
void _RotateR(PNode pParent)
{
// pSubL: pParent的左孩子
// pSubLR: pParent左孩子的右孩子，注意：该
PNode pSubL = pParent->_pLeft;
PNode pSubLR = pSubL->_pRight;
// 旋转完成之后，30的右孩子作为双亲的左孩子
pParent->_pLeft = pSubLR;
// 如果30的左孩子的右孩子存在，更新亲双亲
if(pSubLR)
pSubLR->_pParent = pParent;
// 60 作为 30的右孩子
pSubL->_pRight = pParent;
// 因为60可能是棵子树，因此在更新其双亲前必须先保存60的双亲
PNode pPParent = pParent->_pParent;
// 更新60的双亲
pParent->_pParent = pSubL;
// 更新30的双亲
pSubL->_pParent = pPParent;
// 如果60是根节点，根新指向根节点的指针
if(NULL == pPParent)
{
_pRoot = pSubL;
pSubL->_pParent = NULL;
}
else
{
// 如果60是子树，可能是其双亲的左子树，也可能是右子树
if(pPParent->_pLeft == pParent)
pPParent->_pLeft = pSubL;
else
pPParent->_pRight = pSubL;
}
// 根据调整后的结构更新部分节点的平衡因子
pParent->_bf = pSubL->_bf = 0;
}

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

对于以下情况，单纯的左单旋或者右单旋是无法解决的：

这个时候就要对其先进行右单旋，此时就变成了左单旋的模式，在对其进行左单旋就ok了，我们先以一个简单的例子为例子：

此时我们先把90那个结点右单旋，就变成了parent=2，cur=1的模式，就可以左单旋了。

下面我们来看看过程图：

其实这里的本质就是：

所以旋转后平衡因子的更新和旋转前cur的平衡因子有关
cur为0：

cur为-1：

cur为1：

代码实现：

void RotateRL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        int bf = curleft->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 0)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            cur->_bf = 1;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

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

  这里和上面的情况也是类似的，jrm可以自己画图分析啦~
过程图如下：

void RotateRL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        int bf = curleft->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 0)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            cur->_bf = 1;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

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

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
   当pSubR的平衡因子为1时，执行左单旋
   当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
   当pSubL的平衡因子为-1是，执行右单旋
   当pSubL的平衡因子为1时，执行左右双旋

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

insert的完整代码：

bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            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--;
            }
            else // if (cur == parent->_right)
            {
                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)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }
    void RotateL(Node* parent)
    {
        ++_rotateCount;
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = cur;
        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
        parent->_bf = cur->_bf = 0;
    }
    void RotateR(Node* parent)
    {
        ++_rotateCount;
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        parent->_left = curright;
        if (curright)
            curright->_parent = parent;
        Node* ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;
        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
        parent->_bf = cur->_bf = 0;
    }
    void RotateRL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        int bf = curleft->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 0)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            cur->_bf = 0;
            curleft->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            cur->_bf = 1;
            curleft->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
    void RotateLR(Node* parent)
    {
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        int bf = curright->_bf;
        RotateL(parent->_left);
        RotateR(parent);
        if (bf == 0)
        {
            parent->_bf = 0;
            cur->_bf = 0;
            curright->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 1;
            cur->_bf = 0;
            curright->_bf = 0;
        }
        else if (bf == 1)
        {
            parent->_bf = 0;
            cur->_bf = -1;
            curright->_bf = 0;
        }
    }

四.AVL树的删除(了解)

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。至于具体的实现，有时间在更新吧！

五.AVL树的验证:

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1.二叉搜索树的验证：

中序遍历即可，若有序，就说明为二叉搜索树

2.验证其为平衡树：

a.每个节点子树高度差的绝对值不超过1

b.节点的平衡因子是否计算正确

int Height()
    {
        return Height(_root);
    }
    int Height(Node* root)
    {
        if (root == nullptr)
            return 0;
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    bool IsBalance()
    {
        return IsBalance(_root);
    }
    bool IsBalance(Node* root)
    {
        if (root == nullptr)
            return true;
        int leftHight = Height(root->_left);
        int rightHight = Height(root->_right);
        if (rightHight - leftHight != root->_bf)
        {
            cout << "平衡因子异常:" <<root->_kv.first<<"->"<< root->_bf << endl;
            return false;
        }
        return abs(rightHight - leftHight) < 2
            && IsBalance(root->_left)
            && IsBalance(root->_right);
    }

总的来说，要写这个验证就是为了检验我们代码里面的bug，说实话这段代码挺长的，如果代码出现问题我们一个一个调试去看会非常的难受，这也是一种调试技巧吧！

总结

这就是AVL树的实现，个人感觉难度还是上了很多的。以后我也要多多复习这一部分。

  更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

专栏订阅：
每日一题
C语言学习
算法
智力题
初阶数据结构
Linux学习
C++学习
更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！