【C++】从「树」到「平衡」：全面解密 AVL 树的奥秘与实现

Ne0inhk

— 18 min read
【C++】从「树」到「平衡」：全面解密 AVL 树的奥秘与实现

个人主页:起名字真南的ZEEKLOG博客

个人专栏:

目录

前言

AVL树是一种自平衡的二叉搜索树，它的名字来源于它的发明者G.M. Adelson-Velsky和E.M. Landis，两位前苏联的科学家在论文《An algorithm for the organization of information》中发表了它。

1 AVL树的概念

在AVL树中，任一节点的两棵子树的高度差不超过1，确保了树的高度始终保持在O(log n)范围内，从而提高了查找、插入和删除操作的效率。

主要特点：

  • 平衡因子：每个节点的平衡因子定义为其右子树高度减去左子树高度。平衡因子的取值只能是-1、0或1。当插入或删除节点导致某个节点的平衡因子超出此范围时，需要通过旋转操作来恢复平衡。
  • 旋转操作：为了维护AVL树的平衡性，主要采用以下四种旋转操作：
    • 单右旋（LL旋转）：用于左子树的左子树插入导致的不平衡。
    • 单左旋（RR旋转）：用于右子树的右子树插入导致的不平衡。
    • 先左后右旋（LR旋转）：用于左子树的右子树插入导致的不平衡。
    • 先右后左旋（RL旋转）：用于右子树的左子树插入导致的不平衡。

这些旋转操作通过调整节点的位置，重新平衡树结构，确保AVL树的高度保持在对数级别，从而保证操作的高效性。
AVL树在需要频繁查找、插入和删除操作的应用中表现出色，广泛应用于数据库和文件系统等领域。

在这里插入图片描述


如图所示，这是一课需要进行旋转的AVL树，需要旋转的点就是10，因为它的平衡因子绝对值大于一不满足平衡二叉搜索树的条件，没有节点上面的数字就是它的平衡因子(Balance factor)

2 AVL树的实现

我们想要实现AVL树就需要先清除AVL树的构成，它是由节点，和树一起构成的。

2.1 AVL树的结构

  • 节点的定义：
    • 需要包含关键字段，包括键值对(key , value)、左右节点的指针、父亲节点的指针、以及平衡因子(_bf)
  • 示例代码
#include<iostream>usingnamespace std;template<classK,classV>structAVLTreeNode{ pair<K,V> _kv; AVLTreeNode<K,V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;int _balance_factor;AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balance_factor(0)};
  • 树的定义
    • 包含节点，还有根节点
  • 代码示例
template<classK,classV>classAVLTree{typedef AVLTreeNode<K,V> Node;public://实现树的各种操作private: Node* _root =nullptr;};

我们可以发现在这串代码中并没有构造函数，是因为树是由节点和根节点指针构成的，在构造时会调用节点的构造函数，并且我们给根节点nullptr的缺省值。

2.2 AVL树的插入

2.2.1 插入的大概过程

  1. 首先需要找到合适的插入位置，通过比较Key的大小，是向左还是向右找到当前为空的节点然后进行插入
  2. 在我们调节平衡因子的时候出现了不平衡需要旋转以后，旋转的本质就是调节平衡，降低子树的高度，所以不会影响上一层，插入结束，但是需要更新旋转以后子树各个节点的平衡因子。

因为插入了新的节点所以会引起平衡因子的变化，如果新增节点在父亲节点的右侧则+1，反之则-1，然后继续向上调整如果父亲节点在爷爷节点的右侧则爷爷节点+1，反之则-1，一直到平衡因子为2/-2或者平衡因子为0，又或者平衡因子调整到的了根节点就不需要继续调整。其中如果平衡因子为2/-2则需要进一步的进行旋转。

在这里插入图片描述


1.：需要进行旋转调整，平衡因子绝对值为2
2： 不需要继续向上调整，平衡因子变为0
3： 不需要进行平衡调整，因为已经调整到的根节点

2.2.2 插入节点以及更新平衡因子的代码实现

boolInsert(const pair<K,V>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* cur = _root; Node* parent =nullptr;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}}//此时cur为nullptr节点，parent为它的父亲节点 cur =newNode(kv);//我们链接的一直都是指针所以我们进行比较的时候都使用kvif(kv.first > parent->_kv.first){ parent->_right = cur;}else{ parent->_left = cur;}//最后在将父亲节点互相链接 cur->_parent = parent;}

代码解释：
首先我们要先对树的根节点进行判断是否为空树，如果为空则直接构造一个根节点，如果不为空则进行下一步骤，根据插入节点Key的大小进行比较找到空指针，大于往右走，小于往左走，一直到找到最后一个叶子节点，此时的叶子节点为parent，接着继续比较kv对象和叶子节点的Key值，如果大于则插入在右边，小于则插入在左边。最后将新插入的节点与父亲节点链接起来。

接下来我们开始更新平衡因子

//因为此时的父亲节节点在插入之前是最后一层的节点，//插入之后变成了倒数第二层的节点所以需要对他的平衡因子进行修改while(parent){if(cur == parent->_left) parent->_balance_factor--;else parent->_balance_factor++;//更新完成之后需要进行判断是否进行向上调整if(parent->_balance_factor ==0){//停止更新break;}elseif(parent->_balance_factor ==1|| parent->_balance_factor ==-1){//继续向上更新 cur = parent; parent = cur->_parent;}elseif(parent->_balance_factor ==2|| parent->_balance_factor ==-2){//平衡因子为2/-2，不再进行向上调整，需要进行旋转//旋转代码,见下文}else{assert(false)}}returntrue;

代码解释：在插入一个新的节点以后我们需要更新一下平衡因子，首先要进行判断，新插入的节点是在父亲的右边还是左边，如果右边+1反之**-1**。调整完成之后我们还需要进行判断更新后的平衡因子是否满足结束调节及平衡因子为0，以及是否到达了根节点(因为在向上调整的过程中当cur为根节点时根节点的父亲节点为nullptr，此时我们的while循环条件是parent不为空，所以我们在判断的时候不需要判断是否到达了根节点)。如果不满足结束条件就是parent的平衡因子为1/-1，继续向上调整，如果为2/-2则需要进行旋转。

2.3 AVL树的旋转

在 AVL 树中，平衡因子 是定义为 右子树高度减去左子树高度

  • 平衡条件：AVL 树的每个节点的平衡因子必须保持在 [-1, 0, 1] 之间。
    • BF = 0：左右子树高度相等。
    • BF = -1：左子树比右子树高 1。
    • BF = 1：右子树比左子树高 1。

当平衡因子超出范围（即 BF < -1 或 BF > 1）时，需要通过旋转操作来恢复平衡。

2.3.1 单旋调整

左旋 (RotateL)
  • 触发条件：
    • 当前节点（parent）的 平衡因子 BF == 2，即右子树高度比左子树高 2。
    • 且右子节点（subR）的平衡因子为 1。
  • 旋转效果：
    • 右子节点（subR）成为新的子树根。
    • 当前节点（parent）成为右子节点的左子树。
    • 平衡因子调整：
      • 旋转后，parent._bf = 0，subR._bf = 0。

代码实现：

voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parnet; Node* pParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(pParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(parent == pParent->_right){ pParent->_right = surR;}else{ pParent->_left = surR;} subR->_parent = pParent;} parent->_balance_factor =0; subR->_balance_factor =0;}

旋转前后示例：
插入导致失衡：

 parent 10 \ subR 20 \ 30

左旋后：

 subR 20 / \ parent 10 30
在这里插入图片描述


代码解释：
首先我们需要清楚在进行左单旋的时候的前置条件参数parent节点的平衡因子由1->2，它的右子树subR的平衡因子由0->1，这表明在插入节点之前他的右子树subR是平衡的也就是他可有一个左节点subRL，所以我们在开始进行旋转之前要提前记录好这些节点的指针，方便后续的调整，我们从全局的思维来看，旋转点是parent，我们首先要把subRL节点传到parent节点的右边，不要忘了链接subRL的父亲节点，为了避免对空指针进行访问所以我们需要进行判断，接下来我们要判断旋转因子是否为根节点，我们定义了一个pParent节点，如果他为nullptr则parent为根节点，所以我们需要进行更新，如果不为空我们需要判断parent是pParent的左节点还是右节点因为parent被旋转以后subR称为新的旋转子树的跟需要与pParent进行链接。
最后我们需要更新平衡因子如图所示我们可以直观的看出来更新以后的平衡因子parent，subR都为0。

右旋 (RotateR)
  • 触发条件：
    • 当前节点（parent）的 平衡因子 BF == -2，即左子树高度比右子树高 2。
    • 且左子节点（subL）的平衡因子为 -1。
  • 旋转效果：
    • 左子节点（subL）成为新的子树根。
    • 当前节点（parent）成为左子节点的右子树。
    • 平衡因子调整：
      • 旋转后，parent._bf = 0，subL._bf = 0。

代码实现：

voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* pParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(pParent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(pParent->_right = parent){ pParent->_right = subL;}else{ pParent->_left = subL;} subL->_parent = parent;} parent->_balance_factor =0; subL->_balance_factor =0;}

旋转前后示例：
插入导致失衡：

 parent 30 / subL 20 / 10

右旋后：

 subL 20 / \ parent 10 30
在这里插入图片描述


代码解释：
首先我们需要清楚在进行右单旋的时候的前置条件参数parent节点的平衡因子由1->2，它的左子树subL的平衡因子由0->1，这表明在插入节点之前他的左子树subL是平衡的也就是他可有一个右节点subLR，所以我们在开始进行旋转之前要提前记录好这些节点的指针，方便后续的调整，我们从全局的思维来看，旋转点是parent，我们首先要把subLR节点传到parent节点的左边，不要忘了链接subLR的父亲节点，为了避免对空指针进行访问所以我们需要进行判断，接下来我们要判断旋转因子是否为根节点，我们定义了一个pParent节点，如果他为nullptr则parent为根节点，所以我们需要进行更新，如果不为空我们需要判断parent是pParent的左节点还是右节点因为parent被旋转以后subR称为新的旋转子树的跟需要与pParent进行链接。
最后我们需要更新平衡因子如图所示我们可以直观的看出来更新以后的平衡因子parent，subL都为0。

2.3.2 双旋调整

左-右双旋 (RotateLR)
  • 触发条件：
    • 当前节点（parent）的 平衡因子 BF == -2，即左子树高度比右子树高 2。
    • 且左子节点（subL）的 平衡因子 BF == 1，即左子树的右子树高度更高。
  • 旋转效果：
    • 第一步：对左子节点（subL）进行左旋。
    • 第二步：对当前节点（parent）进行右旋。
    • 平衡因子调整：
      • 根据左旋后中间节点（subLR）的平衡因子进行分配。

旋转前后示例：
插入导致失衡：

 parent 30 / subL 10 \ subLR 20

左-右双旋后：

 subLR 20 / \ subL parent 10 30 
voidRotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right;int bt = subLR->_balance_factor;RotateL(parent->_left);RotateR(parent);if(bf ==0){ subL->_balance_factor =0; parent->_balance_factor =0; subLR->_balance_factor =0;}elseif(bf ==1){ subL->_balance_factor =-1; parent->_balance_factor =0; subLR->_balance_factor =0;}elseif(bf ==-1){ subL->_balance_factor =0; parent->_balance_factor =1; subLR->_balance_factor =0;}else{assert(false);}}
在这里插入图片描述


代码解释：
我们在进行左右双旋的时候前置条件是当前子树的根节点平衡因子为-2，左子树的平衡因子为1，如图所示10为当前子树的根节点在8节点的后面插入一个元素为9的节点所以在左子树5的平衡因子变为1，这个时候我们需要将5节点作为一棵树此时我们需要把5节点进行左旋，8变成根节点5变成他的左节点，然后从整体来看又是一个需要右旋的场景这个时候我们的旋转因子就是10，将10右旋，8的右节点变成了10的左节点，其实从整体来看，左右双旋的本质就是将新增节点(9)的父亲节点(8)变成根节点8的父亲节点变成了它的左节点，pParent(10)变成了它的右节点，然后将8的左右节点分别变成了parent的右节点和pParent的左节点。最后注意在调节平衡因子的时候bf为新增节点的父亲节点的平衡因子，如图所示如果增加以后它的平衡因子为0则双方都不变，如果为1说明增加的是右节点，这个右节点会变成parent的左节点因为parent下降了两层但是右边有一个节点所以平衡因子变成了1但是因为又增加了一个左节点所以变成了0，subL本来右边两层节点，左边一层节点变成了只有左边一个节点，如果为-1，就说明新增的是左节点变成了subL的右节点因为subLR变成了根节点subL的右节点新增和减少抵消还是为0，因为parent没有新增节点并且左边降低了两层右边还是相对于有一层所以平衡因子变为1。

右-左双旋 (RotateRL)
  • 触发条件：
    • 当前节点（parent）的 平衡因子 BF == 2，即右子树高度比左子树高 2。
    • 且右子节点（subR）的 平衡因子 BF == -1，即右子树的左子树高度更高。
  • 旋转效果：
    • 第一步：对右子节点（subR）进行右旋。
    • 第二步：对当前节点（parent）进行左旋。
    • 平衡因子调整：
      • 根据右旋后中间节点（subRL）的平衡因子进行分配。

旋转前后示例：
插入导致失衡：

 parent 10 \ subR 30 / subRL 20

右-左双旋后：

 subRL 20 / \ subR parent 10 30 
voidRotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left;int bf = subRL->_balance_factor;RotateR(parent->_right);RotateL(parent);if(bf ==0){ subR->_balance_factor =0; parent->_balance_factor =0; subRL->_balance_factor =0;}elseif(bf ==1){ subR->_balance_factor =0; parent->_balance_factor =-1; subRL->_balance_factor =0;}elseif(bf ==-1){ subR->_balance_factor =1; parent->_balance_factor =-1; subRL->_balance_factor =0;}}
在这里插入图片描述


代码解释:
进行右左双旋的时候parent节点的平衡因子是2它的右子树节点subR的平衡因子为-1，此时进行右左双旋，结合图片原理同上。

2.3.3 平衡因子调整总结

插入节点时的旋转调整：
  • 旋转后，平衡因子一般重置为 0。
  • 如果旋转前中间节点的平衡因子为非零，需要根据其具体值调整相关节点的平衡因子。
删除节点时的旋转调整：
  • 删除节点后需要更新平衡因子，并可能导致新的不平衡，需要重复旋转。

2.3.4 AVL 树平衡因子和旋转的核心点

  1. 平衡因子范围：AVL 树中每个节点的平衡因子始终在 [-1, 1] 之间。
  2. 旋转的目标：调整平衡因子，确保子树高度差不超过 1。
  3. 递归调整：插入或删除可能影响父节点，调整需要递归向上传播，直至根节点或满足平衡条件。

2.4 AVL树的查找

AVL树为平衡二叉树所以查找的效率是O(logN)
Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}

代码解释：
我们通过比较key值的大小，大的往右走，小的往左走找到了直接返回指针即可。

2.5 AVL树平衡检测

想验证我们实现的AVL树是否合格，我们通过检查左右子树的高度差进行反向验证即可，在这里我们使用递归的方式来计算左右子树的长度。
int_Height(Node* root){if(root ==nullptr){return0;}int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}bool_IsBalanceTree(Node* root){if(root ==nullptr){returntrue;}int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);int diff = rightHeight - leftHeight;if(abs(diff)>=2){returnfalse;}if(diff != root->_balance_factor){returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

代码解释：
通过使用递归的方式计算出每颗子树的高度，通过比较两个子树的高度差来判断他是否是平衡的，并且用差值还可以判断根节点的平衡因子是否异常，两个子树的差值就应该是根节点的平衡因子，如果两棵树都是AVL树那么这整颗树就一定是AVL树

2.6 AVL树的删除

AVL树的删除和二叉搜索树的删除同理，只不过需要删除之后检查平衡因子如果平衡因子不符合则需要进行旋转，

链接: 二叉搜索树博客

Read more

蓝桥杯手把手教你备战（C/C++ B组）（最全面！最贴心！适合小白！）

蓝桥杯手把手教你备战（C/C++ B组）（最全面！最贴心！适合小白！）

比赛环境：网盘资源分享 通过网盘分享的文件：蓝桥杯比赛环境 链接: https://pan.baidu.com/s/1eh85AW-y83ibCmEo8ByBwA?pwd=1234 提取码: 1234 1 常见问题答疑 1.1 蓝桥杯含金量高不高？ 说起蓝桥杯，不得不提ACM。 ACM是国际大学生程序设计竞赛（ACM-ICPC），被誉为计算机领域的“奥运会”，是世界上，规模最大、水平最高、最具影响力的国际大学生程序设计竞赛。 ACM难度较高，当然含金量也更高， 那么蓝桥杯的含金量肯定比不过ACM，但是其具有独特的优势。 蓝桥杯难度更低，更易拿奖，同时在计算机行业具有较高认可度。 ACM适合那些智商高或者编程经验丰富（学习算法1年以上）的选手参赛。而蓝桥杯适合小白，适合期望快速获得编程领域一个认可证书而没有太多时间投入的参赛者。 1.2 获奖到底难不难？ 蓝桥杯分为省赛和国赛。 省赛时： 与你竞争的是同省的人，所以获奖难度与你所在的省份有一定关系。 强省(

By Ne0inhk
使用现代C++构建高效日志系统的分步指南

使用现代C++构建高效日志系统的分步指南

使用现代C++构建高效日志系统的分步指南 * 1. 确定日志系统的需求和目标 * 2. 设计日志系统的架构 * 3. 实现阶段 * 3.1 实现日志管理器（LogManager） * 3.2 实现日志记录器（Logger） * 3.3 实现日志格式化器（Formatter） * 3.4 实现日志输出器（Outputter） * 3.5 实现日志文件轮转 * 3.6 实现异常处理 * 3.7 实现性能优化 * 4. 测试和验证 * 5. 文档编写 * 6. 总结 在软件开发中，日志系统扮演着关键角色，帮助开发者记录程序运行状态、调试问题以及监控系统性能。使用现代C++构建一个高效且灵活的日志系统，不仅可以提升开发效率，还能增强程序的可维护性和可靠性。以下是构建这样一个日志系统的详细分步指南： 1. 确定日志系统的需求和目标

By Ne0inhk
C++ 继承：面向对象的代码复用核心机制

C++ 继承：面向对象的代码复用核心机制

C++ 继承：面向对象的代码复用核心机制 💡 学习目标：掌握继承的基本语法与核心特性，理解不同继承方式的访问权限控制，能够通过继承实现代码复用与扩展。 💡 学习重点：继承的语法格式、三种继承方式的区别、基类与派生类的关系、继承中的构造与析构顺序。 一、继承的概念与核心价值 ✅ 结论：继承是 C++ 面向对象三大特性之一，允许一个类派生类继承另一个类基类的属性和行为，实现代码复用，同时支持派生类在基类基础上扩展新功能。 继承的核心价值体现在两个方面： 1. 代码复用：避免重复编写相同的成员变量和成员函数，降低代码冗余度 2. 功能扩展：派生类可以在基类的基础上新增属性和方法，满足更复杂的业务需求 生活中的继承示例：学生和老师都属于“人”，都有姓名、年龄等属性和吃饭、睡觉等行为。可以先定义 Person 基类，再让 Student 和 Teacher 继承 Person，并各自扩展专属功能。 二、继承的基本语法与实现 2.1

By Ne0inhk
C++之多态

C++之多态

多态 * 什么是多态？ * 多态的定义及实现 * 多态的构成条件 * 虚函数 * 虚函数的重写/覆盖 * 关键技术原理 * 最佳实践指南 * 虚函数重写 * 协变 * 析构函数的重写 * override和final关键字 * 纯虚函数和抽象类 * 多态的原理 * 多态是如何实现的 * 1. 虚函数表（vtable） * 虚函数表知识要点 * 2. 虚函数的声明 * 3. 多态的实现过程 * 动态绑定与静态绑定 什么是多态？ 多态（Polymorphism）是面向对象编程的三大核心特性之一（封装、继承、多态），源于希腊语"多种形态"。在C++中，它允许我们使用统一的接口处理不同类型的对象，显著提高了代码的灵活性和可扩展性。 核心概念 1. 同一接口，多种形态 不同的对象可以通过相同的方法名调用，但实际执行的逻辑由对象自身的类决定。 2. 解耦调用与实现 调用者只需关注接口（方法名和参数）

By Ne0inhk