【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

【大数据存储与管理】分布式文件系统HDFS：06 HDFS的数据读写过程

【大数据存储与管理】分布式文件系统HDFS：06 HDFS的数据读写过程

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈大数据技术原理与应用 ⌋ ⌋ ⌋专栏系统介绍大数据的相关知识，分为大数据基础篇、大数据存储与管理篇、大数据处理与分析篇、大数据应用篇。内容包含大数据概述、大数据处理架构Hadoop、分布式文件系统HDFS、分布式数据库HBase、NoSQL数据库、云数据库、MapReduce、Hadoop再探讨、数据仓库Hive、Spark、流计算、Flink、图计算、数据可视化，以及大数据在互联网领域、生物医学领域的应用和大数据的其他应用。 【GitCode】专栏资源保存在我的GitCode仓库：https://gitcode.com/Morse_Chen/BigData_principle_application。 文章目录 * 一、读数据的过程 * 二、写数据的过程 * 小结 在介绍 HDFS 的数据读写过程之前，需要简单介绍一下相关的类。FileSystem 是一个通用文件系统的抽象基类，可以被分布式文件系统继承，所有可能使用

By Ne0inhk

python满屏无限弹窗表白代码

开发过程 一、准备工作 首先，确保你的电脑上已经安装了Python环境。我们需要安装Tkinter是Python标准库中的一个GUI（Graphical User Interface，图形用户界 面）工具包，其目的是为Python开发者提供快捷创建GUI应用程序的方式。 二、编写代码 接下来，我们将通过编写一个简单的Python脚本来实现满屏无限弹窗的效果。以下是一个基本的示例代码： import tkinter as tk import random as ra import threading as td import time as ti import sys # 定义爱心文字列表，增加多样性 love_texts = [ '我喜欢你', '❤️', '喜欢你', 'love

By Ne0inhk

最新AI-Python自然科学领域机器学习与深度学习技术

技术点目录 * 一、科研数据类型与预处理 夯实建模起点：理解模型本质，规范预处理流程 * 二、模型评估、验证与不确定性量化 科研可信度的基石：不止于准确率 * 三、高维与复杂结构数据降维 从高维噪声中提取主导模态 * 四、时频分析与谱方法 揭示周期、突变与多变量协同机制 * 五、高级回归建模：超越线性假设 超越线性假设，适配多样响应类型 * 六、机器学习核心算法 高精度预测与非线性预测工具箱 * 七、可解释人工智能（XAI） 让模型“说出理由”：支持科学归因与机制推断 * 八、深度学习：感知与表征 处理图像与光谱 * 九、深度学习进阶：序列、生成与注意力 建模动态演化、生成模拟与长程依赖 * 十、时空数据建模技术 专门应对自然系统的核心挑战：时空依赖与耦合 * 了解更多 ———————————————————————————— 随着观测技术、数值模拟与计算基础设施的迅猛发展，地球系统科学、

By Ne0inhk
【原创实践】Python 将 Markdown 文件转换为 Word（docx）完整实现

【原创实践】Python 将 Markdown 文件转换为 Word（docx）完整实现

Python 将 Markdown 文件转换为 Word（docx）完整实现 在实际开发中，经常会遇到将 Markdown 文档转换为 Word（.docx）的需求，例如： * 技术文档从 Markdown 迁移到 Word * 自动生成可下载的 Word 报告 与 Dify、FastAPI 等系统结合做文档导出 本文基于 python-docx + markdown + BeautifulSoup，实现一个不依赖接口、直接读取 Markdown 文件并生成 Word 文件的完整方案，支持常见 Markdown 语法。 参考链接 https://mp.weixin.qq.com/s/vyz5d9Hya9UEEEvOiro9Vg 一、实现思路说明 整体转换流程如下：

By Ne0inhk