【数据结构＆C++】超详细一文带小白轻松全面理解 [ 二叉平衡搜索树-AVL树 ]—— [从零实现＆逐过程分析＆代码演示&简练易懂]-阿里云开发者社区

一.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证 每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

平衡因子是-1，左比右高1；平衡因子是1，右比左高1；平衡因子是0，左右一样高

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O ( l o g 2 n ) O(log_2 n)O(log2n)，搜索时间复杂度O(l o g 2 n log_2 nlog2n)。

二.AVL树节点的定义(代码演示)

除了基本的左右孩子节点与数据外，还需要引入平衡因子

由于平衡因子取决于左右子树相对高度，所以节点本身 要能够返回父亲节点 ——> 要设置指向父亲节点的指针

注意AVL树节点是三叉链

template<class T>
struct AVLTreeNode
{
 AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
 , _data(data), _bf(0)
 {}
 AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
 AVLTreeNode<T>* _pRight;  // 该节点的右孩子
 AVLTreeNode<T>* _pParent; // 该节点的父亲节点
 T _data;
 int _bf;                  // 该节点的平衡因子
};

三.AVL树的基本操作：插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

AVL树的插入过程：

与二叉搜索树同理，二叉搜索树博客传送门：https://blog.csdn.net/YYDsis/article/details/134374001?spm=1001.2014.3001.5501

平衡因子的变化步骤：

新增在左，parent平衡因子减减

新增在右，parent平衡因子加加

平衡因子==0，高度不变，直接break

平衡因子==1/-1，高度改变-> 会影响祖先 -> 需要继续沿着到根节点root的路径向上更新

平衡因子==2/-2，高度改变＆ 树不再平衡 ->会影响祖先->需要对parent所在子树进行旋转操作，让其平衡（旋转部分放在part4中详解）

向上更新，直到根节点（根节点parent==0）

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;
    }
//1. 按照二叉搜索树的方式插入新节点
    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. 调整节点的平衡因子
    while (parent)//向上更新，直到根节点（根节点parent==0）
    {
      if (cur == parent->_left)// 1.新增在左，parent平衡因子减减
      {
        parent->_bf--;
      }
      else // if (cur == parent->_right)
      {
        parent->_bf++;//2.新增在右，parent平衡因子加加
      }
      if (parent->_bf == 0)//3.平衡因子==0，高度不变，直接break
      {
        // 更新结束
        break;
      }
            //4.平衡因子==1/-1，高度改变-> 会影响祖先 -> 需要继续沿着到根节点root的路径向上更新
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        // 继续往上更新
        cur = parent;
        parent = parent->_parent;
      }
               //平衡因子==2/-2，高度改变＆ 树不再平衡 ->会影响祖先->
               //需要对parent所在子树进行 旋转 操作，让其平衡
      else if (parent->_bf == 2 || parent->_bf == -2)
      {
        // 子树不平衡了，需要旋转     （旋转部分为何这么设计放在part4中详解）
        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;
  }

四.AVL树的核心操作：旋转

根据part3中avl树的基本操作"插入"，以下情况会出现旋转

平衡因子==2/-2，高度改变＆ 树不再平衡 ->会影响祖先->需要对parent所在子树进行旋转操作，让其平衡（旋转部分放在part4中详解）

所以一共有四种情况分别如下图所示：

旋转要注意以下三点：
1. 保持这颗树还是搜索树
2. 变成平衡树＆降低其高度
3. 节点是三叉链的形式，旋转后要注意节点链接

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

分析：

如下图所示，新节点插入较高右子树的右侧时候，整体会发生“向左的单旋”

核心操作：

cur的左给parent的右，parent再成为cur的左
cur->_right = parent;
parent->_parent = cur;

注意：节点是三叉链的形式，旋转后要注意节点链接

要设置 祖父节点pparent指向parent，parent的_parent节点指向parent

情况1：特殊情况，父母节点为根节点，空指向cur

情况2：正常情况，祖父节点指向cur

注意：平衡因子变化

观察以上图中变化可知，我们只需要 在最后将cur和parent都调整为0就行：

parent->_bf = cur->_bf = 0;

代码展示：

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 = cur;
    if (parent == _root)//特殊情况，父母节点为根节点，空指向cur
    {
      _root = cur;
      cur->_parent = nullptr;
    }
    else//正常情况，祖父节点指向cur
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = cur;
      }
      else
      {
        ppnode->_right = cur;
      }
      cur->_parent = ppnode;
    }
    parent->_bf = cur->_bf = 0;
  }

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

相关细节与上面【1】中 “右右：左单旋” 一致，下面展示代码

代码展示：

void RotateR(Node* parent)
  {
    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;
  }

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

引入：

我们观察【1】【2】情况，其都是左左/右右，发生逆向的旋转（左左->往右转）（右右->往左转）

而【3】【4】这种双旋的情况呢？如下图所示，观察可以发现，当其是 新节点插入较高左子树的右侧时 ,形成了一个折线

进一步观察后，我们发现有 三种情况 会触发双旋,可以观察 curright的平衡因子 判断，分别是：
1. curright就是新增节点 bf == 0
2. b处新增节点 bf == -1
3. c处新增节点 bf == 1

注意：平衡因子变化

我们根据 三种触发双旋的情况 ，对他们平衡因子变化进行分析

1. curright就是新增节点
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;

2. b处新增节点
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;

3. c处新增节点
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;

void RotateLR(Node* parent)
  {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    int bf = curright->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    if (bf == 0)//1. curright就是新增节点 bf == 0
    {
      parent->_bf = 0;
      cur->_bf = 0;
      curright->_bf = 0;
    }
    else if (bf == -1)//2. b处新增节点 bf == -1
    {
      parent->_bf = 1;
      cur->_bf = 0;
      curright->_bf = 0;
    }
    else if (bf == 1)//3. c处新增节点 bf == 1
    {
      parent->_bf = 0;
      cur->_bf = -1;
      curright->_bf = 0;
    }
  }

注意：双旋的本质（表现）

60的左边给了30的右边

60的右边给了90的左边

60成了这棵树的根

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

相关细节与上面【2】中 “左右：先左单旋再右单旋【双旋】” 一致，下面展示代码

代码展示：

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

五.AVL树的验证

1. 验证其为二叉搜索树

如果其通过 中序遍历 可得到一个有序的序列，就说明为其为二叉搜索树

2. 验证其为平衡树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

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

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

六.AVL树的性能＆引入红黑树

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这
样可以保证查询时高效的时间复杂度，即l o g 2 ( N ) log_2 (N)log2(N)。但是如果要对AVL树做一些结构修改的操
作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数
据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。 因此需要
引入红黑树，传送门如下所示：

红黑树博客传送门：

七.AVL树的完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  pair<K, V> _kv;
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  int _bf;  // balance factor
  AVLTreeNode(const pair<K, V>& kv)
    :_kv(kv)
    ,_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_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)
    {
      _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;
    }
  }
  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);
  }
private:
  Node* _root = nullptr;
public:
  int _rotateCount = 0;
};

【数据结构＆C++】超详细一文带小白轻松全面理解 [ 二叉平衡搜索树-AVL树 ]—— [从零实现＆逐过程分析＆代码演示&简练易懂]

一.AVL树的概念

二.AVL树节点的定义(代码演示)

三.AVL树的基本操作：插入

四.AVL树的核心操作：旋转

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

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

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

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

五.AVL树的验证

1. 验证其为二叉搜索树

2. 验证其为平衡树

六.AVL树的性能＆引入红黑树

七.AVL树的完整代码

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构＆C++】超详细一文带小白轻松全面理解 [ 二叉平衡搜索树-AVL树 ]—— [从零实现＆逐过程分析＆代码演示&简练易懂]

一.AVL树的概念

二.AVL树节点的定义(代码演示)

三.AVL树的基本操作：插入

四.AVL树的核心操作：旋转

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

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

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

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

五.AVL树的验证

1. 验证其为二叉搜索树

2. 验证其为平衡树

六.AVL树的性能＆引入红黑树

七.AVL树的完整代码

热门文章

最新文章

相关课程

相关电子书