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

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

2023-12-28 40
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构＆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++分析
数据结构avl
C++代码
你的小笔记本YY
目录
相关文章
ephemerals__
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
43 16
java冯坚持
|
27天前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
16 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
27天前
|
存储 算法 数据管理
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
这篇文章通过需求分析、代码实现和测试验证，详细介绍了二叉排序树的创建、遍历和删除操作，以及二叉平衡树（AVL）的自平衡特性和单旋转操作，旨在提高树结构在数据管理中的效率和性能。
java冯坚持
24 0
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
nanshaws
|
1月前
|
Linux C语言 C++
vsCode远程执行c和c++代码并操控linux服务器完整教程
这篇文章提供了一个完整的教程，介绍如何在Visual Studio Code中配置和使用插件来远程执行C和C++代码，并操控Linux服务器，包括安装VSCode、安装插件、配置插件、配置编译工具、升级glibc和编写代码进行调试的步骤。
nanshaws
156 0
vsCode远程执行c和c++代码并操控linux服务器完整教程
Dylaniou
|
24天前
|
Java C++
【数据结构】探索红黑树的奥秘：自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理，介绍其五大原则，并通过图解和代码示例展示其内部机制。同时，对比红黑树与二叉查找树的性能差异，帮助读者更好地理解这两种数据结构的特点和应用场景。
Dylaniou
23 0
java冯坚持
|
27天前
|
编解码 算法 Java
数据结构与算法学习十九：赫夫曼树树（图文很详细）、赫夫曼编码、应用实践（数据压缩、数据解压）、这一章自我感觉看懂就好。。。
赫夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩和编码。
java冯坚持
31 0
java冯坚持
|
27天前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
22 0
Codelinghu
|
29天前
05（数据结构考研）树相关操作代码
05（数据结构考研）树相关操作代码
Codelinghu
27 0
何雨晨
|
30天前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
何雨晨
12 0
椰椰椰耶
|
1月前
【数据结构】翻转、平衡、对称二叉树，最大深度、判断两棵树是否相等、另一棵树的子树
【数据结构】翻转、平衡、对称二叉树，最大深度、判断两棵树是否相等、另一棵树的子树
椰椰椰耶
30 0