【C++】—— 详解AVL树

序言

前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个
共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

（一）AVL树的概念

1、AVL树的由来

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下；

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：

• 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度
  

2、AVL树的特点

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

1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
   

下图所示的平衡二叉树，右边的是不平衡的二叉树：

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O(log_2 n)，搜索时间复杂度O(log_2 n）。

3、平衡因子

平衡因子（Balance Factor）是用于衡量二叉树节点的左子树和右子树之间的平衡程度的指标。它定义为左子树的高度减去右子树的高度（或者相反），即：

• 平衡因子 = 右子树的高度 - 左子树的高度（反过来也可以）

平衡因子的值可以是正、零或负，具体含义如下：

1. 如果平衡因子为正数，意味着左子树比右子树高。
2. 如果平衡因子为零，意味着左子树和右子树具有相同的高度。
3. 如果平衡因子为负数，意味着右子树比左子树高。

对于 AVL树 来说，平衡因子在每个节点上都需要保持在 -1、0、1 的范围内。如果平衡因子超出了这个范围，就表示树不再平衡，需要进行旋转等操作来恢复平衡。

例如下面这棵树表示的就是一棵 AVL树，结点外的值即表示的是该结点的平衡因子：

因此，综上我们可以知道平衡因子的引入就是为了确保树的高度保持在较小的范围内，从而提高树的查询、插入和删除等操作的性能。通过保持平衡因子在指定范围内，可以确保树结构相对平衡，避免出现极度不平衡的情况，导致操作的时间复杂度恶化。

（二）AVL树的插入

二叉排序树保证平衡的基本思想如下：

1. 每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡；
2. 若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点 A ，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意：每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。

1、插入操作的思想理解

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么

AVL树的插入过程可以分为两步：

• 1. 按照二叉搜索树的方式插入新节点
• 2. 调整节点的平衡因子

大致思想如下：

1. 先按照二叉搜索树的规则将节点插入到AVL树中
2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
破坏了AVL树的平衡性

pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

• 1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
• 2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
  

此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2

• 1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
• 2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
• 3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

2、AVL树的旋转

因此上述操作如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1️⃣ LL平衡旋转（右单旋转）

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

【说明】

1. 上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡；
2. 此时要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，即将左子树往上提；
3. 这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可
   

在旋转过程中，有以下几种情况需要考虑：

1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树

• 如果是根节点，旋转完成后，要更新根节点
• 如果是子树，可能是某个节点的左子树，也可能是右子树
  

2️⃣ RR平衡旋转（左单旋转）

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

【说明】

1. 上图在插入前，AVL树是平衡的，新节点插入到60的右子树(注意：此处不是右孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡；
2. 此时要让30平衡，只能将30右子树的高度减少一层，左子树增加一层，即将右子树往上提；
3. 这样30转下来，因为30比60小，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可

3️⃣ LR平衡旋转（先左后右双旋转）

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

 【说明】

1. 由于在 90 的左孩子（ L ）的右子树（ R ）上插入新结点， 90 的平衡因子由 -1变为 -2，导致以 90 为根的子树失去平衡；
2. 需要进行两次旋转操作，先左旋转后右旋转。先将 90 结点的左孩子 30 的右子树的根结点 60 向左上旋转提升到 30 结点的位置，然后把该 60 结点向右上旋转提升到 90 结点的位置

4️⃣ RL平衡旋转（先右后左双旋转）

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

  【说明】

1. 上图在插入前，AVL树是平衡的，新节点插入到60的右子树(注意：此处不是右孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡；
2. 由于在 30 的右孩子（ R ）的左子树（ L ）上插入新结点， 30 的平衡因子由 1变为2，导致以 30为根的子树失去平衡；
3. 需要进行两次旋转操作，先右旋转后左旋转。先将 30结点的右孩子 90的左子树的根结点 60向右上旋转提升到 90结点的位置，然后把该 60结点向左上旋转提升到 30结点的位置，
   

【注意】：LR 和 RL旋转时，新节点究竟是插入 60 的左子树还是右子树都不影响旋转过程

3、构造示例

以关键字序列（15,3,7,10,9,8）构造一棵平衡二叉树的过程为例：

【说明】

• 插入7后导致不平衡，最小不平衡子树的根为15，插入位置为其左孩子的右子树，故执行 LR 旋转，先左后右双旋转，调整后的结果如图所示；
• 当插入9后导致不平衡，最小不平衡子树的根为15，插入位置为其左孩子的左子树，故执行 LL 旋转，右单旋转；
• 插入8后导致不平衡，最小不平衡子树的根为7，插入位置为其右孩子的左子树，故执行 RL 旋转，先右后左双旋转。

（三）AVL树的删除（了解）

与平衡二叉树的插入操作类似，以删除结点 w 为例来说明平衡二叉树删除操作的步骤：

1）用二叉排序树的方法对结点 w 执行删除操作。

2）从结点 w 开始，向上回溯，找到第一个不平衡的结点 z （即最小不平衡子树）; y 为结点 z 的高度最高的孩子结点： x 是结点 y 的高度最高的孩子结点。

3）然后对以 z 为根的子树进行平衡调整，其中 x 、 y 和 z 可能的位置有4种情况：

• y 是 z 的左孩子， x 是 y 的左孩子（ LL ，右单旋转）;
• y 是 z 的左孩子， x 是 y 的右孩子（ LR ，先左后右双旋转）;
• y 是 z 的右孩子， x 是 y 的右孩子（ RR ，左单旋转）;
• y 是 z 的右孩子， x 是 y 的左孩子（ RL ，先右后左双旋转）。

这四种情况与插入操作的调整方式一样。不同之处在于，插入操作仅需要对以 z 为根的子树进行平衡调整；而删除操作就不一样，先对以 z 为根的子树进行平衡调整，如果调整后子树的高度减1，则可能需要对 z 的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减1)。

以删除下图的结点32为例：

【说明】

1. 由于32位叶结点，直接删除即可，向上回溯找到第一个不平衡的结点44（即z）；
2. z的高度最高的孩子结点为 78（即y），y的高度最大的孩子结点为50（即x），满足RL情况，先右后左双旋转，调整后的结果即为上图所示

（四）代码实现

1、AVL树节点的定义

template<class K,class V>
class 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)
  {}
};

2、左单旋转

代码如下：

//左旋转
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    Node* ppnode = parent->_parent;
    subR->_left = parent;
    parent->_parnet = subR;
    if (ppnode == nullptr)
    {
      _root = subR;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subR;
      }
      else
      {
        ppnode->_right = subR;
      }
      subR->_parent = ppnode;
    }
    // 根据调整后的结构更新部分节点的平衡因子
    parent->_bf = subR->_bf = 0;
  }

3、右单旋转

代码如下：

//右旋转
  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 (ppnode == nullptr)
    {
      _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;
  }

4、先左后右双旋转

大家结合下图以及上述讲LR时的图进行思考，我相信就不难解决：

代码如下：

//LR操作
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    if (bf == 1)
    {
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      parent->_bf = 1;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

5、先右后左双旋转

跟上述同理：

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);
    }
  }

（五）AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这

样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操

作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，

有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数

据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

代码链接：AVL的实现

总结

以上便是关于本期AVL的树的详细介绍，感谢大家的观看与支持！！！