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

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

2023-12-28 41
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构＆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
你的小笔记本YY
目录
相关文章
sunrr
|
7天前
|
算法 安全 C++
提高C/C++代码的可读性
提高C/C++代码的可读性
sunrr
21 4
梦笔生花伟
|
10天前
|
Ubuntu Linux Shell
C++ 之 perf+火焰图分析与调试
【11月更文挑战第6天】在遇到一些内存异常的时候，经常这部分的代码是很难去进行分析的，最近了解到Perf这个神器，这里也展开介绍一下如何使用Perf以及如何去画火焰图。
梦笔生花伟
46 5
nanshaws
|
1月前
|
存储 算法 搜索推荐
对二叉堆的简单分析，c和c++的简单实现
这篇文章提供了对二叉堆数据结构的简单分析，并展示了如何在C和C++中实现最小堆，包括初始化、插入元素、删除最小元素和打印堆的函数，以及一个示例程序来演示这些操作。
nanshaws
34 19
梦笔生花伟
|
1月前
|
Ubuntu Linux Shell
C++ 之 perf+火焰图分析与调试
【10月更文挑战第8天】在遇到一些内存异常的时候，经常这部分的代码是很难去进行分析的，最近了解到Perf这个神器，这里也展开介绍一下如何使用Perf以及如何去画火焰图。
梦笔生花伟
28 1
nanshaws
|
1月前
|
Linux C语言 C++
vsCode远程执行c和c++代码并操控linux服务器完整教程
这篇文章提供了一个完整的教程，介绍如何在Visual Studio Code中配置和使用插件来远程执行C和C++代码，并操控Linux服务器，包括安装VSCode、安装插件、配置插件、配置编译工具、升级glibc和编写代码进行调试的步骤。
nanshaws
212 0
vsCode远程执行c和c++代码并操控linux服务器完整教程
游客qeoynko2nmbgk
|
2月前
|
C++
继续更新完善：C++ 结构体代码转MASM32代码
继续更新完善：C++ 结构体代码转MASM32代码
游客qeoynko2nmbgk
33 0
游客qeoynko2nmbgk
|
2月前
|
C++ Windows
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
游客qeoynko2nmbgk
20 0
游客qeoynko2nmbgk
|
2月前
|
C++
2合1，整合C++类（Class）代码转换为MASM32代码的平台
2合1，整合C++类（Class）代码转换为MASM32代码的平台
游客qeoynko2nmbgk
18 0
yantuguiguziPGJ
|
2月前
|
前端开发 C++ Windows
C++生成QML代码与QML里面集成QWidget
这篇文章介绍了如何在C++中生成QML代码，以及如何在QML中集成QWidget，包括使用Qt Widgets嵌入到QML界面中的技术示例。
yantuguiguziPGJ
36 0
ephemerals__
|
16天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
91 9