【数据结构】AVL树-阿里云开发者社区

前言

在C++的STL标准库中的set、map、multiset和multimap的底层实现都是二叉搜索树。

而进行搜索数据的方式有：

暴力搜索。
二分搜索（缺陷：二分查找需要有序数组，伴随着插入，维护的成本较高）
二叉搜索树（缺陷：在极端场景下会退化成链表，其效率无法保证）
二叉平衡搜索树
多叉平衡搜索树：B树
哈希表

由于二叉搜索树的自身缺陷，假如往树中插入的元素有序或者接近有序，二叉树就会退化成为单支树，时间复杂度为O(N)，因此map、set等关联式容器的底层结构式对二叉树进行了平衡处理，及采用平衡树来实现。而AVL树的实现就是二叉平衡平衡树。

AVL树的概念

二叉搜索树虽然可以缩短查找的效率，但是如果数据有序或者接近有序，二叉搜索树就会退化成为单支树，查找元素相当于在顺序表里查找，效率低下。

在1962年，俩位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果可以保证每一个节点的左右子树高度之差的绝对值不超过1（需要对树中的节点进行调整），即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者式空树，或者是具有以下性质的二叉搜索树：

其左右子树都是AVL树
左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）

平衡因子的计算方式：平衡因子=右子树高度-左子树高度

AVL树的本质是高度平衡二叉搜索树，其二叉树只有在满二叉树的情况，平衡因子才会相等，否则进行增加与删除操作的时候，平衡因子肯定会被改变。

如果一棵二叉搜索树是高度平衡的，其就是AVL树。

如果有n个节点，其高度可以保持在O(logN)，搜索时间复杂度O(logN)。

当为满二叉树：2^h-1=N
AVL树：2^h-x= N(x的范围：1

AVL树的模拟实现

AVL树的基本框架

template<class k, class v>
struct AVLTreeNode
{
  //构造
  AVLTreeNode(const k& date)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
 
  AVLTreeNode<k, v>* _left;
  AVLTreeNode<k, v>* _right;
  AVLTreeNode<k, v>* _parent;
  pair<k,v> _kv;
  int _bf;//平衡因子
};
 
template<class k, class v>
class AVLTree
{
  typedef AVLTreeNode<k,v> Node;
  AVLTree()
    :_node(nullptr)
  {}
 
private:
  Node* _root;
};

AVL树的插入

AVL树就是在二叉搜索树的基础之上引入了平衡因子，所以在插入节点的同时可以参考AVL树，然后通过结合平衡因子来解决问题。

其核心步骤分为三步：

按照二叉搜索树的方式插入新节点
调整节点的平衡因子
根据平衡因子观察是否达到平衡，如果没有则进行旋转。

插入新节点

  bool Insert(const pair<k,v>& kv)
  {
    //插入新节点
    if (_root == nullptr)
    {
      _root = new Node<kv>;
      return true;
    }
 
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new Node<kv>;
    if (cur->_kv.first > kv.first)
    {
      parent->_left = cur;
    }
    else if (cur->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      assert(false);
    }
    cur->_parent = parent;
    //计算平衡因子
  }

平衡因子的计算

当新的节点插入之后，AVL树的平衡性可能会被破坏，此时就需要更新破坏因子，并检测是否破坏了AVL树的平衡性。

平衡因子=右子树的高度-左子树的高度。

观察这棵已经是AVL树的每一个平衡因子，当cur插入之后，parent的平衡因子一定会被调整，在插入cur之前，parent的平衡因子一共会分成三种情况：-1/0/1。

当插入cur之后，可能出现的结果如下：

新增在左，parent的平衡因子减1。
新增在右，parent的平衡因子加1。
更新后parent的平衡因子==0，说明parent所在的子树高度不变，不会影响祖先，不用再继续沿着root的路径往上更新。
更新后parent的平衡因子==1 or ==-1，说明parent所在的子树高度变化，会对祖先造成影响，需要再继续沿着到root的路径往上更新。
更新后parent的平衡因子==2 or ==-2，说明parent所在的子树高度已经变化，并且不平衡，需要立刻对parent所在的子树进行旋转，让其平衡。
平衡因子向上更新到根节点——>插入结束。

我们在更新平衡因子的时候可以发现，平衡因子相当于是用于检测这棵AVL树的平衡的，平衡因子的区间是[-2,2]。

  bool Insert(const pair<k,v>& kv)
  {
    //插入新节点
    if (_root == nullptr)
    {
      _root = new Node<kv>;
      return true;
    }
 
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new Node<kv>;
    if (cur->_kv.first > kv.first)
    {
      parent->_left = cur;
    }
    else if (cur->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      assert(false);
    }
    cur->_parent = parent;
    //更新平衡因子
    while (parent)
    {
      //第一、二步：更新parent的平衡因子
      if (cur == parent->_left)
      {
        parent->_bf--;
      }
      else if (cur == parent->_right)
      {
        parent->_bf++;
      }
      //第三步：更新后parent的平衡因子==0
      if (parent->_bf == 0)
      {
        break;
      }
      //第四步：更新后parent的平衡因子==1 or ==-1
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = parent;
        parent = cur->_parent;
      }
      //第五步：更新后parent的平衡因子==2 or ==-1
      else if (parent->_bf == 2 || parent->_bf == -2)
      {
        //旋转
        break;
      }
      else
      {
        assert(false);
      }
    }
  }

AVL树的旋转

在一棵原本是是AVL平衡树中插入一个节点，可能会造成不平衡，此时必须调整树的结构，使之平衡。

根据节点的插入位置的不同，AVL树的旋转会分为4种：

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

下面将进行详细讲解：

首先，旋转之前需要注意的俩个问题：

保持其是搜索树
变成平衡树且降低这个子树的高度。

左单旋

在上述的情况中，h的可能值为0,1,2,3,4...，a，b，c是符合AVL树的子树。

当h==2的时候，a和b是x，y，z中的一种，c只能是z，然后在这种情况下，才会导致M、N之间的旋转。

在插入前的可能形状的组合：3*3*1=9种；新元素可能插入的位置存在4种；这样当h==2的时候，合计情况有36种。

【注意】我们在插入新元素之后，会导致parent的平衡因子成为2，cur的平衡因子成为1，在这种情况下，需要左单旋转操作。

在进行左单旋操作的核心操作是：

将b转移到M的右子树之下；
如果b不等于空，将b的父亲转换为M；如果b为空，则不进行操作；
将M转移到N的左子树之下；
记录M的父亲
将M的父亲转换为N；
将记录的N的原父转换为N的父亲；并判断M是原父的左子还是右子。

这里可以总结：需要进行改变的数据一共有：parent的parent的孩子的指向，parent的右孩子的指向，parent的父亲指向，cur的左孩子指向，cur的父亲指向，cur的左孩子的父亲指向。

代码展示：

//左单旋
void RotateL(Node* parent)
{
  Node* cur = parent->_right;
  Node* curleft = cur->_left;
 
  parent->_right = curleft;
  if (curleft)
  {
    curleft->_parent = parent;
  }
  cur->_left = parent;
  Node* pparent = parent->_parent;
  parent->_parent = cur;
  if (pparent == nullptr)
  {
    _root = cur;
    cur->_parent = nullptr;
  }
  else
  {
    if (pparent->_left == parent)
    {
      pparent->_left = cur;
    }
    else //if(pparent->_right == parent)
    {
      pparent->_right = cur;
    }
    cur->_parent = pparent;
  }
  parent->_bf = cur->_bf = 0;
}

右单旋

右单旋与左单旋的方式类似，方式如图：

代码展示：

//右单旋
void RotateR(Node* parent)
{
  Node* cur = parent->_left;
  Node* curright = cur->_right;
  parent->_left = curright;
  if (curright)
  {
    curright->_parent = parent;
  }
  cur->_right = parent;
  Node* pparent = parent->_parent;
  parent->_parent = cur;
  if (pparent == nullptr)
  {
    _root = cur;
    cur->_parent = nullptr;
  }
  else
  {
    if (pparent->_left == parent)
    {
      pparent->_left = cur;
    }
    else
    {
      pparent->_right = cur;
    }
    cur->_parent = pparent;
  }
  parent->_bf = cur->_bf = 0;
}

右左旋转

在了解完左单旋和右单选之后，我们基本对这俩种单旋转方式有了基本的认识，这俩种单旋的方式都是直线插入的，而在进行折线插入的时候需要实现另外一种方法。

【注意】我们可以在c位置的左子树位置或右子树位置添加节点。

当h==2的时候：

a和d是x，y，z中的任意一棵子树，c只能是z这棵子树；

这样合计下来：一共有3*3*4=36种情况。（3*3是a，d之前的组合；4是当h等于2的时候，可以新增的数据个数）。

此时可以发现，使用单旋的方式已经不能解决问题，需要使用双旋转的方式来解决问题：

以60为旋转点，进行右单旋转
以30为旋转点，进行左单旋转

右左双旋转的结果本质上是：

60为根
60的左边是30
60的右边是90
60的左边给了30的右边
60的右边给了30的左边

通过对图例的了解，当h==0的时候，60的左右子树都为空，即60是新增的元素；当h>0的时候，在60的左子树或者60的右子树新增元素，才会构成右左旋转。

处理节点的平衡因子的时候，可以将平衡因子分成3份，判断的主要条件是60在旋转之前的的平衡因子：

当60旋转之前的平衡因子为0，则旋转之后30，60，90的平衡因子都为0；
当60旋转之前的平衡因子为1，则旋转之后60，90的平衡因子为0，30的平衡因子为-1；
当60旋转之前的平衡因子为-1，则旋转之后60，30的平衡因子为0，90的平衡因子为1；

则进行代码展示：

  //左右旋转
  void RotateLR(Node* parent)
  {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    int bf = curright->_bf;
 
    RotateL(cur);
    RotateR(parent);
 
    if (bf == 0)
    {
      curright->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 0;
    }
    else if (bf == 1)
    {
      curright->_bf = 0;
      parent->_bf = -1;
      cur->_bf = 0;
    }
    else if (bf == -1)
    {
      curright->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }

左右旋转

左右旋转与右左旋转的思路相同，即：先对30进行左单选，然后再对90进行右单旋，旋转之后考虑平衡因子的更新。

处理节点的平衡因子的时候，可以将平衡因子分成3份，判断的主要条件是60在旋转之前的的平衡因子：

当60旋转之前的平衡因子为0，则旋转之后30，60，90的平衡因子都为0；
当60旋转之前的平衡因子为1，则旋转之后30，60的平衡因子为0，30的平衡因子为-1；
当60旋转之前的平衡因子为-1，则旋转之后60，90的平衡因子为0，90的平衡因子为1；

则进行代码展示：

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

AVL树的验证

AVL树由于是再二叉搜索树的基础之上加入了平衡性的因素，因此如果需要验证AVL树，可以分为俩步：

1.验证是否为二叉搜索树：

如果中序遍历可以得到一个有序的序列，就可以说明是二叉搜索树。

2.验证是否为平衡树

每一个节点子树的高度差的绝对值不会超过1（注意节点中如果没有平衡因子）
节点的平衡因子的计算是否正确

  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 leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
 
    if (rightHeight - leftHeight != root->_bf)
    {
      cout << "平衡因子异常：" << root->_kv.first << "->" << root->_bf << endl;
      return false;
    }
    
    return abs(rightHeight - leftHeight) < 2
      && IsBalance(root->_left)
      && IsBalance(root->_right);
        
  }

AVL树的删除

由于AVL树也是二叉搜索树，可以按照二叉搜索树的方式将节点删除，步骤如下：

按照搜索树的规则查找节点删除
更新平衡因子，当cur为0的时候，更新parent的平衡因子
出现异常旋转。

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，要求每一个节点的左右子树高度之差的绝对值不能超过1，这样可以保证在查询的时候具有高效性，时间复杂度为logN。

但是对于AVL树的一些结构修改的操作性能是非常低的，就比如：插入时需要维护其平衡，旋转的次数比较多，更差的是在删除的时候，有可能一直让旋转持续到根的位置。

代码展示

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
 
template<class k, class v>
struct AVLTreeNode
{
  //构造
  AVLTreeNode(const pair<k,v>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
 
  AVLTreeNode<k, v>* _left;
  AVLTreeNode<k, v>* _right;
  AVLTreeNode<k, v>* _parent;
  pair<k,v> _kv;
  int _bf;//平衡因子
};
 
template<class k, class v>
class AVLTree
{
public:
  typedef AVLTreeNode<k,v> Node;
  AVLTree()
    :_root(nullptr)
  {}
 
  bool Insert(const pair<k,v>& kv)
  {
    //插入新节点
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
 
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new Node(kv);
    if (parent->_kv.first > kv.first)
    {
      parent->_left = cur;
    }
    else if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      assert(false);
    }
    cur->_parent = parent;
    //更新平衡因子
    while (parent)
    {
      //第一、二步：更新parent的平衡因子
      if (cur == parent->_left)
      {
        parent->_bf--;
      }
      else if (cur == parent->_right)
      {
        parent->_bf++;
      }
      //第三步：更新后parent的平衡因子==0
      if (parent->_bf == 0)
      {
        break;
      }
      //第四步：更新后parent的平衡因子==1 or ==-1
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = parent;
        parent = cur->_parent;
      }
      //第五步：更新后parent的平衡因子==2 or ==-1
      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)
  {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
 
    parent->_right = curleft;
    if (curleft)
    {
      curleft->_parent = parent;
    }
    cur->_left = parent;
    Node* pparent = parent->_parent;
    parent->_parent = cur;
    if (pparent == nullptr)
    {
      _root = cur;
      cur->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = cur;
      }
      else //if(pparent->_right == parent)
      {
        pparent->_right = cur;
      }
      cur->_parent = pparent;
    }
    parent->_bf = cur->_bf = 0;
  }
  //右单旋
  void RotateR(Node* parent)
  {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    parent->_left = curright;
    if (curright)
    {
      curright->_parent = parent;
    }
    cur->_right = parent;
    Node* pparent = parent->_parent;
    parent->_parent = cur;
    if (pparent == nullptr)
    {
      _root = cur;
      cur->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = cur;
      }
      else
      {
        pparent->_right = cur;
      }
      cur->_parent = pparent;
    }
    parent->_bf = cur->_bf = 0;
  }
  //左右旋转
  void RotateLR(Node* parent)
  {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    int bf = curright->_bf;
 
    RotateL(cur);
    RotateR(parent);
 
    if (bf == 0)
    {
      curright->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 0;
    }
    else if (bf == 1)
    {
      curright->_bf = 0;
      parent->_bf = -1;
      cur->_bf = 0;
    }
    else if (bf == -1)
    {
      curright->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }
  //右左旋转
  void RotateRL(Node* parent)
  {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    int bf = curleft->_bf;
 
    RotateR(cur);
    RotateL(parent);
 
    if (bf == 0)
    {
      curleft->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 0;
    }
    else if (bf == 1)
    {
      curleft->_bf = 0;
      parent->_bf = 0;
      cur->_bf = -1;
    }
    else if (bf == -1)
    {
      curleft->_bf = 0;
      parent->_bf = 0;
      cur->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }
 
  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 leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
 
    if (rightHeight - leftHeight != root->_bf)
    {
      cout << "平衡因子异常：" << root->_kv.first << "->" << root->_bf << endl;
      return false;
    }
    
    return abs(rightHeight - leftHeight) < 2
      && IsBalance(root->_left)
      && IsBalance(root->_right);
        
  }
private:
  Node* _root;
};

【数据结构】AVL树

前言

AVL树的概念

AVL树的模拟实现

AVL树的基本框架

AVL树的插入

插入新节点

平衡因子的计算

AVL树的旋转

左单旋

右单旋

右左旋转

左右旋转

AVL树的验证

AVL树的删除

AVL树的性能

代码展示

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】AVL树

前言

AVL树的概念

AVL树的模拟实现

AVL树的基本框架

AVL树的插入

插入新节点

平衡因子的计算

AVL树的旋转

左单旋

右单旋

右左旋转

左右旋转

AVL树的验证

AVL树的删除

AVL树的性能

代码展示

热门文章

最新文章

相关课程

相关电子书