c++的学习之路：26、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)如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间复杂度O(log_2 n)。

下面的图就是一颗AVL树，画的有点抽象，0、-1、1就是平衡因子

二、四种旋转

1、左单旋

如下图就是左单选的过程，就是b肯定是比30大，这时就可以把b连接到30的右边，然后把60变成根节点，30变成60的左节点，就是如下图这种变化，然后这时就需要进行更新平衡因子，就可以进行左旋了，电脑画图太麻烦了，我就放一下我的手图了。

2、右单旋

右单选，与做单选相反就是把右边的进行放在左边，然后原理都差不多，就是b的位置肯定是比60小然后就放到30左边，然后在进行旋转进行连接在，这样就可以右旋了，这里我就不画电脑的图了，用我的手图代替了

3、左右双旋

左右双旋就是先进行做单选在进行右单选，这种情况的形状就是<就是这种的就是一个小于号，当直接左旋或者右旋就会把树给扭曲了，就不是平衡了们就是先把他变成/这种形状然后在进行右单选就可以平衡这个二叉树了，下面就是我画的图了，就不用电脑画了。

4、右左双旋

这里就是和上面那个双旋相反，就是先把>这个形状变成\这种，然后就是先进行右单选，在进行做单选，就可以把这颗树进行平衡了，这里就不进行画图了，因为原理都差不多。

三、代码实现

1、节点创建

这个节点是利用三叉链进行维护的，数据存储也就是和搜索二叉树的原理，因为搜索二叉树会右歪脖子树，所以这里就只是平衡，但是他的原理还是差不多，所以这里也是利用键值对进行一个pair容器的创建，然后在创建一个bf进行充当平衡因子进行维护。

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;//平衡因子，用来平衡AVL树，使他相对像完全二叉树
    AVLtreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};

2、插入

插入的代码就是和搜索二叉树原理差不多，也就是大于在右边小于在左边，这里创建也是先进行插入，没有节点的时候就插入在根，有的时候就去遍历寻找，大的在右边小的在左边，然后进行插入，在进行更新平衡因子，这里是利用一个节点记录当前的父节点时候，就可以进行循环进行更新平衡因子，等于2或者-2的时候就需要进行旋转了，这时有四种情况

1、父节点=2、当前节点=1就是进行左单旋

2、父节点=-2、当前节点=-1就是右单旋

3、父节点=2、当前节点=-1时，就是双旋了，左右双旋

4、父节点=-1、当前节点=1时，就是右左双旋

下方代码就是我写的插入，也有注释

bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)//如果是空节点直接申请，然后返回true
        {
            _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;//找不到就返回false
            }
        }
        cur = new Node(kv);//创建新的节点
        if (parent->_kv.first > kv.first)//如果小于就插入在右边
        {
            parent->_left = cur;
        }
        else if (parent->_kv.first < kv.first)//如果大于就插入到左边
        {
            parent->_right = cur;
        }
        cur->_parent = parent;//记录一下父节点的地址
        while (parent)//平衡因子的更新，持续到根
        {
            if (cur == parent->_right)//判断新的节点在父节点的左右，如果在右边平衡因子就++，如果在左边就--
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            if (parent->_bf == 1 || parent->_bf == -1)//如果父节点的平衡因子等于1或者-1，接着更新
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            else if(parent->_bf==0)//如果平衡因子等于0就退出
            {
                break;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)//超长了，准备旋转了，有四种情况
            {
                if (parent->_bf == 2 && cur->_bf == 1)//当父节点的平衡因子等于2当前节点的平衡因子等于1时                
                {                                      //就是相当于右边是一条直线时，然后进行左旋
                    RotateL(parent);//调用左旋函数
                }
                else if (parent->_bf == -2 && cur->_bf == -1)//当父平衡因子等于-2当前节点平衡因子等于-1时
                {                                                //就是左边时一条直线的情况时，然后进行右旋
                    RotateR(parent);//调用右旋函数
                }
                else if (parent->_bf == -2 && cur->_bf == 1)//当父节点平衡因子等于-2时，当前节点的平衡因子等于-1时
                {                                            //就是相当于一条折现，就是<这个形状，需要旋转两次，先左旋在右旋
                    RotateLR(parent);//调用先左旋在右旋的函数
                }
                else if (parent -> _bf == 2 && cur->_bf == -1)//当父节点平衡因子等于2时，当前节点平衡因子等于-1时
                {                                            //就是相当于>这个形状，也是需要旋转两次，先进性右旋在进行左旋
                    RotateRL(parent);//调用先右旋在左旋的函数
                }
                else
                {
                    assert(false);//上述情况都没出现，就说明树已经出现问题了，这里直接利用断言直接报错，断死
                }
                break;
            }
            else
            {
                assert(false);//这里就是更新平衡因子失败，也就是说上述都没，也就是直接报错，因为树也是出现错误了
            }
        }
    return true;
    }

3、旋转

下面这段代码就是四种旋转，在左右单旋后，更新平衡因子是0，双旋的平衡因子需要根据具体条件具体实现，具体怎么是先把的下面都有注释。

void RotateL(Node* parent)//左旋
    {
        Node* subR = parent->_right;//记录父节点的右侧，用来后续旋转
        Node* subRL = subR->_left;//记录subR的左侧，这个节点比父节点大，比subR小
        parent->_right = subRL;//因为这个节点比父节点大，所以连接父节点在右边
        if (subRL)
            subRL->_parent = parent;//如果subRL节点不是空姐点就把他的父节点置为父节点
        Node* ppnode = parent->_parent;//记录父节点的父节点
        subR->_left = parent;//旋转把subR的左节点连接为父节点，因为父节点比subR节点小
        parent->_parent = subR;//把父节点的父节点置为subR
        if (ppnode == nullptr)//判断ppnode是否为空也就是之前的父节点是否为根
        {
            _root = subR;//如果是根的话，就把subR置为根，在把subR的父节点置为空
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)//判断ppnode的左节点是否为之前的父节点，如果是就把位置换成subR
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;//判断ppnode的右节点是否为之前的父节点，如果是就把位置换成subR
            }

            subR->_parent = ppnode;//在进行连接subR的父节点
        }
        parent->_bf = subR->_bf = 0;//最后更新平衡因子，因为旋转过后肯定是平衡的所以直接置为0
    }

    void RotateR(Node* parent)//右旋，与上面左旋的原理差不多，就是换个方向
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;
        Node* ppnode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        subL->_bf = parent->_bf = 0;
    }

    void RotateLR(Node* parent)//双旋之先左旋在右旋
    {
        Node* subL = parent->_left;//记录父节点的左侧
        Node* subLR = subL->_right;//记录subL的右侧因为形状是<这样的，然后需要先左旋进行掰直
        int bf = subLR->_bf;//用于记录平衡因子
        RotateL(parent->_left);//利用左旋函数进行左旋，这里就是把父节点的左侧当成父节点传进去，也就是subL
        RotateR(parent);//然后在进行右旋
        if (bf == 1)//更新平衡因子，当前平衡因子如果等于1就把父节点的平衡因子置为0，subLR的为0，因为这个节点在旋转过后
        {            //就会平衡，但是在bf等于1时，左边肯定是有的，所以subL就是-1
            parent->_bf = 0;
            subLR->_bf = 0;
            subL->_bf = -1;
        }
        else if (bf == -1) //在旋转之前平衡因子是-1 的话，在旋转结束时，也就是说明父节点的位置就是需要置为1，因为之前
        {                    //在左，旋转之后就是有右，其他两个就是0
            parent->_bf = 1;
            subLR->_bf = 0;
            subL->_bf = 0;
        }
        else if (bf == 0)//如果都是0的话旋转后也是0就直接更新成0
        {
            parent->_bf = 0;
            subLR->_bf = 0;
            subL->_bf = 0;
        }
        else//如果没有就说明树出现问题了直接断言报错
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)//现右旋在左旋与上面差不多
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 1)
        {
            subR->_bf = 0;
            parent->_bf = -1;
            subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else if (bf == 0)
        {
            subR->_bf = 0;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

4、判断是否平衡

这里还是进行一个封装，因为不太好穿私有变量，所以这里也就是利用函数进行封装了，如下方代码所示，是否出现错误就是判断高度差，也就是左右高度差不超过2，这里如下方代码所示，在代码旁边注释了了我的思路

void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    bool IsBalance()
    {
        return _IsBalance(_root);
    }

    int Height()
    {
        return _Height(_root);
    }
private:
    int _Height(Node* root)//求树的高度
    {
        if (root == NULL)
            return 0;
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    bool _IsBalance(Node* root)//判断是否出现异常，高度差在2以内
    {
        if (root == NULL)
        {
            return true;
        }
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        if (rightH - leftH != root->_bf)//判断平衡因子是否出错
        {
            cout << root->_kv.first << "节点平衡因子异常" << endl;
            return false;
        }
        return abs(leftH - rightH) < 2//这里是因为不知道哪个大所以直接求绝对值
            && _IsBalance(root->_left)//因为每条路都需要求一下所以直接递归去求
            && _IsBalance(root->_right);
    }

    void _InOrder(Node* root)//中序遍历
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }

5、测试

这里是利用随机数进行测试是否是平衡，如下方代码和测试结果。

void test()
{
    srand(time(0));
    const size_t N = 500000;
    AVLTree<int, int> t;
    for (size_t i = 0; i < N; ++i)
    {
        size_t x = rand() + i;
        t.Insert(make_pair(x, x));
        //cout << t.IsBalance() << endl;
    }

    //t.Inorder();

    cout << t.IsBalance() << endl;
    cout << t.Height() << endl;
}

四、代码

#pragma once
 
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;//平衡因子，用来平衡AVL树，使他相对像完全二叉树
  AVLtreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
 
template<class K,class V>
class AVLTree
{
  typedef AVLtreeNode<K,V> Node;//重定义，方便后续节点申请使用
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)//如果是空节点直接申请，然后返回true
    {
      _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;//找不到就返回false
      }
    }
    cur = new Node(kv);//创建新的节点
    if (parent->_kv.first > kv.first)//如果小于就插入在右边
    {
      parent->_left = cur;
    }
    else if (parent->_kv.first < kv.first)//如果大于就插入到左边
    {
      parent->_right = cur;
    }
    cur->_parent = parent;//记录一下父节点的地址
    while (parent)//平衡因子的更新，持续到根
    {
      if (cur == parent->_right)//判断新的节点在父节点的左右，如果在右边平衡因子就++，如果在左边就--
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      if (parent->_bf == 1 || parent->_bf == -1)//如果父节点的平衡因子等于1或者-1，接着更新
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if(parent->_bf==0)//如果平衡因子等于0就退出
      {
        break;
      }
      else if (parent->_bf == 2 || parent->_bf == -2)//超长了，准备旋转了，有四种情况
      {
        if (parent->_bf == 2 && cur->_bf == 1)//当父节点的平衡因子等于2当前节点的平衡因子等于1时       
        {                   //就是相当于右边是一条直线时，然后进行左旋
          RotateL(parent);//调用左旋函数
        }
        else if (parent->_bf == -2 && cur->_bf == -1)//当父平衡因子等于-2当前节点平衡因子等于-1时
        {                       //就是左边时一条直线的情况时，然后进行右旋
          RotateR(parent);//调用右旋函数
        }
        else if (parent->_bf == -2 && cur->_bf == 1)//当父节点平衡因子等于-2时，当前节点的平衡因子等于-1时
        {                     //就是相当于一条折现，就是<这个形状，需要旋转两次，先左旋在右旋
          RotateLR(parent);//调用先左旋在右旋的函数
        }
        else if (parent -> _bf == 2 && cur->_bf == -1)//当父节点平衡因子等于2时，当前节点平衡因子等于-1时
        {                     //就是相当于>这个形状，也是需要旋转两次，先进性右旋在进行左旋
          RotateRL(parent);//调用先右旋在左旋的函数
        }
        else
        {
          assert(false);//上述情况都没出现，就说明树已经出现问题了，这里直接利用断言直接报错，断死
        }
        break;
      }
      else
      {
        assert(false);//这里就是更新平衡因子失败，也就是说上述都没，也就是直接报错，因为树也是出现错误了
      }
    }
  return true;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
 
  int Height()
  {
    return _Height(_root);
  }
private:
  int _Height(Node* root)//求树的高度
  {
    if (root == NULL)
      return 0;
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    return leftH > rightH ? leftH + 1 : rightH + 1;
  }
 
  bool _IsBalance(Node* root)//判断是否出现异常，高度差在2以内
  {
    if (root == NULL)
    {
      return true;
    }
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    if (rightH - leftH != root->_bf)//判断平衡因子是否出错
    {
      cout << root->_kv.first << "节点平衡因子异常" << endl;
      return false;
    }
    return abs(leftH - rightH) < 2//这里是因为不知道哪个大所以直接求绝对值
      && _IsBalance(root->_left)//因为每条路都需要求一下所以直接递归去求
      && _IsBalance(root->_right);
  }
 
  void _InOrder(Node* root)//中序遍历
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }
  void RotateL(Node* parent)//左旋
  {
    Node* subR = parent->_right;//记录父节点的右侧，用来后续旋转
    Node* subRL = subR->_left;//记录subR的左侧，这个节点比父节点大，比subR小
    parent->_right = subRL;//因为这个节点比父节点大，所以连接父节点在右边
    if (subRL)
      subRL->_parent = parent;//如果subRL节点不是空姐点就把他的父节点置为父节点
    Node* ppnode = parent->_parent;//记录父节点的父节点
    subR->_left = parent;//旋转把subR的左节点连接为父节点，因为父节点比subR节点小
    parent->_parent = subR;//把父节点的父节点置为subR
    if (ppnode == nullptr)//判断ppnode是否为空也就是之前的父节点是否为根
    {
      _root = subR;//如果是根的话，就把subR置为根，在把subR的父节点置为空
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)//判断ppnode的左节点是否为之前的父节点，如果是就把位置换成subR
      {
        ppnode->_left = subR;
      }
      else
      {
        ppnode->_right = subR;//判断ppnode的右节点是否为之前的父节点，如果是就把位置换成subR
      }
 
      subR->_parent = ppnode;//在进行连接subR的父节点
    }
    parent->_bf = subR->_bf = 0;//最后更新平衡因子，因为旋转过后肯定是平衡的所以直接置为0
  }
 
  void RotateR(Node* parent)//右旋，与上面左旋的原理差不多，就是换个方向
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* ppnode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;
    }
    subL->_bf = parent->_bf = 0;
  }
 
  void RotateLR(Node* parent)//双旋之先左旋在右旋
  {
    Node* subL = parent->_left;//记录父节点的左侧
    Node* subLR = subL->_right;//记录subL的右侧因为形状是<这样的，然后需要先左旋进行掰直
    int bf = subLR->_bf;//用于记录平衡因子
    RotateL(parent->_left);//利用左旋函数进行左旋，这里就是把父节点的左侧当成父节点传进去，也就是subL
    RotateR(parent);//然后在进行右旋
    if (bf == 1)//更新平衡因子，当前平衡因子如果等于1就把父节点的平衡因子置为0，subLR的为0，因为这个节点在旋转过后
    {     //就会平衡，但是在bf等于1时，左边肯定是有的，所以subL就是-1
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1) //在旋转之前平衡因子是-1 的话，在旋转结束时，也就是说明父节点的位置就是需要置为1，因为之前
    {         //在左，旋转之后就是有右，其他两个就是0
      parent->_bf = 1;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else if (bf == 0)//如果都是0的话旋转后也是0就直接更新成0
    {
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else//如果没有就说明树出现问题了直接断言报错
    {
      assert(false);
    }
  }
 
  void RotateRL(Node* parent)//现右旋在左旋与上面差不多
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == 1)
    {
      subR->_bf = 0;
      parent->_bf = -1;
      subRL->_bf = 0;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      parent->_bf = 0;
      subRL->_bf = 0;
    }
    else if (bf == 0)
    {
      subR->_bf = 0;
      parent->_bf = 0;
      subRL->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  Node* _root = nullptr;
};
 
void test()
{
  srand(time(0));
  const size_t N = 500000;
  AVLTree<int, int> t;
  for (size_t i = 0; i < N; ++i)
  {
    size_t x = rand() + i;
    t.Insert(make_pair(x, x));
    //cout << t.IsBalance() << endl;
  }
 
  //t.Inorder();
 
  cout << t.IsBalance() << endl;
  cout << t.Height() << endl;
}

c++的学习之路：26、AVL树

摘要