备案控制台
开发者社区 开发与运维 文章 正文

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

2023-12-28 30
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构＆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
  • 平衡因子的变化步骤：
  1. 新增在左，parent平衡因子减减
  2. 新增在右，parent平衡因子加加
  3. 平衡因子==0，高度不变，直接break
  4. 平衡因子==1/-1，高度改变-> 会影响祖先 -> 需要继续沿着到根节点root的路径向上更新
  5. 平衡因子==2/-2，高度改变＆ 树不再平衡 ->会影响祖先->需要对parent所在子树进行 旋转 操作，让其平衡 （旋转部分放在part4中详解）
  6. 向上更新，直到根节点（根节点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;
    }
  }
  • 注意：双旋的本质（表现）
  1. 60的左边给了30的右边
  2. 60的右边给了90的左边
  3. 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++
关键词：
C++分析
C++ avl
数据结构树
数据结构分析
C++代码
你的小笔记本YY
目录
相关文章
lge101058
|
6天前
|
存储 测试技术
【数据结构】手把手分析：链式二叉树的实现
【数据结构】手把手分析：链式二叉树的实现
lge101058
16 5
邢仕冲的一亩三分地
|
14天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
邢仕冲的一亩三分地
19 4
邢仕冲的一亩三分地
|
14天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
邢仕冲的一亩三分地
16 1
Eternity._
|
16天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列：数据结构探索之旅
【C++进阶】深入STL之 栈与队列：数据结构探索之旅
Eternity._
20 4
爱喝兽奶的熊孩子
|
16天前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
21 2
爱喝兽奶的熊孩子
|
16天前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
27 2
爱喝兽奶的熊孩子
|
16天前
|
存储 算法 C++
【数据结构与算法】：带你手搓顺序表（C/C++篇）
【数据结构与算法】：带你手搓顺序表（C/C++篇）
爱喝兽奶的熊孩子
20 1
嘎嘎旺
|
4天前
|
C++
【c++】avl树
【c++】avl树
嘎嘎旺
3 0
67vpym2vvkfhs
|
7天前
|
算法
数据结构和算法常见的问题和代码
数据结构和算法常见的问题和代码
67vpym2vvkfhs
9 0
阿旭算法与机器学习
|
17天前
|
存储 机器学习/深度学习 缓存
【数据结构】布隆过滤器原理详解及其代码实现
【数据结构】布隆过滤器原理详解及其代码实现
阿旭算法与机器学习
14 0

热门文章

最新文章

  • 1
    【C语言/数据结构】二叉树（层序遍历|判断完全二叉树|性质）
  • 2
    【C 言专栏】C 语言中的数据结构应用
  • 3
    【数据结构】~顺序表
  • 4
    [数据结构]-红黑树
  • 5
    【数据结构】树和二叉树堆（基本概念介绍）
  • 6
    Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
  • 7
    [数据结构]-map和set
  • 8
    【数据结构】二叉树-堆（top-k问题，堆排序，时间复杂度）
  • 9
    高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
  • 10
    猿创征文｜栈和队列OJ刷题
  • 1
    C++STL（标准模板库）处理学习应用案例
    25
  • 2
    C++语言模板学习应用案例
    17
  • 3
    【C++/Python】Windows用Swig实现C++调用Python（史上最简单详细，80岁看了都会操作）
    49
  • 4
    【C++】VS code如何配置使用C++（手把手教学）
    60
  • 5
    【C++初阶】9. string类的模拟实现
    47
  • 6
    【C++初阶】10. vector的使用及模拟实现
    63
  • 7
    【C++的奇迹之旅（二）】C++关键字&&命名空间使用的三种方式&&C++输入&输出&&命名空间std的使用惯例
    31
  • 8
    【C++】Visual Studio C++ 配置并使用gtest（不好用你捶我）
    92
  • 9
    C/C++test两步完成CMake项目静态分析
    21
  • 10
    推荐一个比较好用的c++版本http协议库-cpp-httplib
    84

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）