【C++】手撕AVL树(上)

简介: 【C++】手撕AVL树(上)

> 作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等

> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:能直接手撕AVL树。

> 毒鸡汤:放弃自己,相信别人,这就是失败的原因。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕



🌟前言  

相信大家肯定听过在C++大名鼎鼎的两颗树,这两颗树分别是AVL树和红黑树,学过的小伙伴听到都是瑟瑟发抖,像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大,正所谓难度越大动力就越大,那本篇我们学习这两棵树的一颗树--AVL树。


⭐主体

学习AVL树咱们按照下面的图解:



🌙AVL树的概念

在计算机科学中,AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。


AVL树的定义

  • 一棵空的树是AVL树
  • 如果T是一棵非空的二叉树,T(L)和T(R)分别是其左子树高和右子树高,那么当T满足以下条件时,T是一棵AVL树,|h(L)-h(R)|<=1,其中h(L)和h(R)分别是T(L)和T(R)的高(简称平衡因子)


AVL树的状态:



AVL树的特性:

  • 一棵n个元素的AVL树,其高度是O(logn)
  • 对于每一个n,n>=0,都存在一棵AVL树
  • 对一棵n元素的AVL搜索树,在O(高度)=O(logn)的时间内可以完成查找
  • 将一个新元素插入一棵n元素的AVL搜索树中,可以得到一棵n+1个元素的AVL树,而且插入用时为O(logn)
  • 一个元素从一棵n元素的AVL搜索树中删除,可以得到一棵n-1个元素的AVL树,而且删除用时为O(logn)


🌙AVL树的结点

  • 按照 KV 模型来构造 AVL 树,需要把结点定义为 三叉链结构(左、右、父)。
  • 构造函数,由于新构造结点的左右子树均为空树,所以将新构造结点的平衡因子初始设置为 0 。


代码示例:

// 创建AVL树的结点
template<class K,class V>
struct 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)
  {}
};


🌙AVL树的插入

其实AVL树插入操作,本质上比二叉搜索树的插入操作多了一个平衡操作

  1. 按照二叉搜索树的方式,找到待插入的位置,然后将新结点插入到该位置。
  2. 调整节点的平衡因子,如果出现不平衡,则需要进行旋转。

当 AVL 树插入一个新结点以后,需要更新插入结点的祖先的平衡因子,因为新结点(也就是叶子结点)的平衡因子为 0,但是它影响的是它的父亲,它父亲的父亲…,所以要更新到祖先结点。



上面的图就需要改变父亲爷爷的平衡因子,我们知道,树的状态有很多,无法穷举,但是我们也有规律可寻,这个规律就在于我们的平衡因子,所以我总结如下:


  • 如果新增结点插入在 parent 的右边,只需要给 parent 的平衡因子 +1 即可
  • 如果新增结点插入在 parent 的左边,只需要给 parent 的平衡因子 -1 即可


当 parent 的平衡因子更新完以后,可能出现三种情况:0,正负 1,正负 2。

(1)parent 的平衡因子为 0

如果parent的平衡因子是0:说明之前parent的平衡因子是1或-1,说明之前parent一边高、一边低;这次插入之后填入矮的那边,parent所在的子树高度不变,不需要继续往上更新。如图:



(2)如果 parent 的平衡因子为正负 1

如果parent的平衡因子是1或者-1:说明之前parent的平衡因子是0,两边一样高,插入之后一边更高,parent所在的子树高度发生变化,继续往上更新

①parent为1



②parent为 -1



(3)如果 parent 的平衡因子为正负 2

平衡因子是2或-2,说明之前parent的平衡因子是1或-1,现在插入严重不平衡,违反规则,需要进行旋转处理


  • 如果parent的平衡因子是2,cur的平衡因子是1时,说明右边的右边比较高,我们需要进行左单旋
  • 如果parent的平衡因子是-2,cur的平衡因子是-1时,说明左边的左边比较高,我们需要进行右单旋
  • 如果parent的平衡因子是-2,cur的平衡因子是1时,我们需要进行左右双旋
  • 如果parent的平衡因子是2,cur的平衡因子是-1时,我们需要进行右左双旋


这里我们就举一个栗子:



代码实现:

public:
  // 插入函数
  bool Insert(const pair<K, V>& kv)
  {
    // 如果AVL树是空树,把插入节点直接作为根节点
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_bf = 0;
      return true;
    }
 
    // 1.按照二叉搜索树的规则插入
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.first) // 待插入节点的key值大于当前节点的key值
      {
        // 往右子树走
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first) // 待插入节点的key值小于当前节点的key值
      {
        // 往左子树走
        parent = cur; 
        cur = cur->_left;
      }
      else // 待插入节点的key值等于当前节点的key值
      {
        return false; // 插入失败,返回false
      }
    }
 
    // 2.当循环结束,说明cur找到了空的位置,那么就插入
    cur = new Node(kv); // 构造一个新节点
    if (parent->_kv.first < kv.first) // 如果新节点的key值大于当前parent节点的key值
    {
      // 就把新节点链接到parent的右边
      parent->_right = cur;
    }
    else // 如果新节点的key值小于当前parent节点的key值
    {
      // 就把新节点链接到parent的左边
      parent->_left = cur;
    }
    cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)
 
    // 3.更新平衡因子,如果出现不平衡,则需要进行旋转
    while (parent) // 最远要更新到根节点去
    {
      if (cur == parent->_right) // 如果cur插在parent的右边,说明parent的右子树增高
      {
        parent->_bf++; // 那么parent的平衡因子要++
      }
      else // 如果cur插在parent的左边,说明parent的左子树增高
      {
        parent->_bf--; // 那么parent的平衡因子要--
      }
 
      // 判断是否更新结束,或者是否需要进行旋转
      if (parent->_bf == 0) // 如果parent的bf等于0,说明左右子树高度一致,就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了)
      {
        // 高度不变,更新结束
        break;
      }
      else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了,说明parent所在的子树高度改变了)
      {
        // 子树的高度变了,就要继续往上更新祖先
        cur = cur->_parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了,子树不平衡了,那么此时需要做旋转处理
      {
        // 旋转的四种处理方式
        // 1.左单旋
        // 2.右单旋
        // 3.左右双旋
        // 4.右左双旋
        
        // 旋转完成,跳出
        break;
      }
      else
      {
        // 如果程序走到了这里,说明在插入节点之前AVL树就存在不平衡的子树,也就是存在平衡因子 >= 2的节点
        // 所以这里加一个断言进行处理
        assert(false);
      }
    }
    // 插入成功,返回true
    return true;
  }




【C++】手撕AVL树(下)     https://developer.aliyun.com/article/1565632

目录
打赏
0
0
0
0
28
分享
相关文章
|
23天前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
56 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
23天前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
40 12
|
23天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
40 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
41 2
|
3月前
|
【C++】AVL树
AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。
77 2
|
5月前
|
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
45 2
|
6月前
|
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
57 5
|
7月前
|
C++
【C++】手撕AVL树(下)
【C++】手撕AVL树(下)
68 1
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
47 2
|
23天前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
62 19
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等