深入理解 AVL 树:自平衡二叉搜索树的原理与实现
二叉搜索树BST是一种经典的数据结构理想情况下查找、插入、删除操作的时间复杂度均为 O(log n)。但它有一个致命缺陷在极端插入顺序下如有序插入二叉搜索树会退化成链表时间复杂度恶化为 O(n)。为了解决这个问题1962 年两位苏联数学家 Adelson-Velsky 和 Landis 提出了一种自平衡二叉搜索树 ——AVL 树以两人姓氏首字母命名。它通过在每次插入和删除后维护树的平衡保证了所有操作的最坏时间复杂度始终为 O(log n)。一AVL树的核心定义1.1AVL树的性质AVL 树本质上是一棵满足以下条件的二叉搜索树1满足二叉搜索树的所有性质左子树所有节点值 根节点值 右子树所有节点值。2树中每个节点的平衡因子的绝对值不超过 1即 |BF| 1。3左右子树也都是 AVL 树。当插入或删除操作导致某个节点的平衡因子超出 [-1, 1] 范围时就需要通过旋转操作来重新恢复平衡。1.2AVL树的平衡因子AVL 树的核心概念是平衡因子Balance Factor, BF它定义为某节点的右子树高度减去左子树的高度。由于左右子树的高度差的绝对值不超过1所以任何节点的平衡因子等于0 / 1 / -1 AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去观察和控制树是否平衡。AVL整体节点数量和分布与完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在O(log n)相比二叉搜索树有了很大提升。二AVL树的实现2.1AVL树的节点结构#includeiostream #includeassert.h using namespace std; templateclass k,class v class AVLTreeNode { public: pairk,v _kv; AVLTreeNodek,v* _left; AVLTreeNodek,v* _right; AVLTreeNodek,v* _parent; int _bf;//balance factor ,平衡因子 AVLTreeNode(const pairk,v kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };这是AVL树的结构节点中的数据使用pairKeyValue存储键值对数据。若存在一个结点root_left代表它的左边的结点该节点的key比root的key小_right代表它的右边的结点该节点的key比root的key大_parent代表它的父结点_bf是这个结点对应的平衡因子的值。2.2AVL树的插入2.2.1AVL树插入一个值的过程1插入一个值的规则要按照二叉搜索树的规则若要插入的值比当前结点大那么要插入的值就在这个结点的右子树上反之就在这个结点的左子树上若找到了一个结点它的值与要插入的值相等就不允许插入这个值了直接返回false插入该值失败。2若新增一个结点只会影响它的祖先结点的高度也就会影响部分祖先结点的平衡因子所以就要更新从该结点到根结点路径上的平衡因子但有些情况只更新部分祖先结点的平衡因子更新到中间就停止了具体是什么情况后面慢慢分析。3在更新平衡因子的过程中若出现了不平衡就要对不平衡的子树旋转旋转之后本质是为了降低子树的高度不会影响上一层所以插入结束。2.2.2平衡因子的更新1更新规则平衡因子右子树高度-左子树高度。只有子树高度变化才会影响当前结点的平衡因子。当我们插入了一个比10小的值5就会插入到它的左子树上10的平衡因子由0变成了-1在插入一个比10大的值1510的平衡因子就变成了0。所以得出一个结论若10结点为parent新增节点在它的左子树上parent平衡因子减一新增结点在它的右子树上parent平衡因子加一。2更新后parent的平衡因子等于0说明更新前parent的平衡因子为-1或者1则更新前parent子树一边高一边低新增结点在低的那边插入后parent子树高度不变不会影响parent的父结点的平衡因子更新结束。3更新后parent的平衡因子等于1或者-1说明更新前parent的平衡因子为0则更新前parent子树两边一样高新增结点后parent所在子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父结点的平衡因子所以要继续向上更新。4更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插⼊结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把 parent子树旋转平衡。2、降低parent子树的高度恢复到插⼊结点以前的高度。所以旋转后也不需要继续往上更新插入结束。插入结点及更新平衡因子代码实现bool insert(const pairk, v p) { Node* root _root; Node* parent nullptr; while (root) { if (root-_key_value.first p.first) { parent root; root root-_left; } else if (root-_key_value.first p.first) { parent root; root root-_right; } else { return false; } } Node* newnode new Node(p); newnode-_parent parent; if (parent nullptr) { _root newnode; } else { if (parent-_key_value.first p.first) { parent-_left newnode; } else if (parent-_key_value.first p.first) { parent-_right newnode; } } //更新平衡因子 Node* cur newnode; while (parent) { if (parent-_left cur) { --parent-_bf; } else { //if (parent-_right cur) 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) { //右单旋 RotateR(parent); } else if (parent-_bf 2 cur-_bf 1) { //左单旋 RotateL(parent); } else if (parent-_bf -2 cur-_bf 1) { //左右双旋 RotateLR(parent); } else if (parent-_bf 2 cur-_bf -1) { //右左双旋 RotateRL(parent); }else { assert(false); } break; }else { assert(false); } } return true; }2.3AVL树插入结点的旋转操作及代码实现旋转之后也要保持搜索树的规则让旋转的树从不平衡变平衡其次降低旋转树的高度。旋转分为四种左单旋 / 右单旋 / 左右双旋 / 右左双旋。2.3.1左单旋此时再新增80结点它所在路径上的祖先结点依次向上更新这颗子树的根节点parent它的平衡因子就变成了2不符合AVL树的规则了。下面的图可以看到这颗子树的右边高就要将parent结点左旋降低树的高度。那怎么判断出是需要左旋的呢若parent的平衡因子为2cur的平衡因子为1parent就需要左旋了。具体怎么左旋下图所示。步骤1先将parent的_right指向cur的左子树若cur的左子树不为空就将cur的左子树的_parent结点指向parent。步骤2将cur的_left指向parent注意要提前保存好parent的_parent结点parentParent因为parent可能只是当前这颗子树的根将parent的_parent指向cur。再判断出parent结点是parentParent结点的_left还是_right判断好了parentParent结点的_left或者_right(具体根据前面的判断)指向curcur的_parent指向parentParent。代码实现void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) { subRL-_parent parent; } subR-_left parent; Node* parentParent parent-_parent; parent-_parent subR; if (parentParent) { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } else { subR-_parent nullptr; _root subR; } parent-_bf subR-_bf 0; }2.3.2右单旋右单旋与左单旋类似旋转步骤示意图及代码如下右旋代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; subL-_right parent; if (subLR) { subLR-_parent parent; } Node* parentParent parent-_parent; parent-_parent subL; if (parentParent) { if (parentParent-_left parent) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } else { _root subL; subL-_parent nullptr; } subL-_bf parent-_bf 0; }2.3.3右左双旋更新到25这个结点平衡因子变成了228的平衡因子是-1。要对28右旋再对25左旋降低树的高度。旋转之前必须提前保存28结点的平衡因子int bf cur-_bf (-1) 。另外还有两种情况1subRL1则bf subRL-_bf1。2subRL-1则bf subRL-_bf-1。右左双旋代码实现//右左双旋 void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; //先保存subRL的平衡因子 int bf subRL-_bf; RotateR(subR); RotateL(parent); if (bf -1) { subRL-_bf 0; parent-_bf 0; subR-_bf 1; } else if (bf 1) { subRL-_bf 0; parent-_bf -1; subR-_bf 0; } else if (bf 0) { subRL-_bf 0; parent-_bf 0; subR-_bf 0; } else { assert(false); } }2.3.4左右双旋1bf0;2bf1;3bf-1;左右双旋代码实现//左右双旋 void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; //先保存subLR的平衡因子 int bf subLR-_bf; RotateL(subL); RotateR(parent); if (bf 1) { subLR-_bf 0; subL-_bf -1; parent-_bf 0; } else if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); } }以上就是AVL树插入一个结点的相关旋转操作。删除一个结点操作后续更新

相关新闻

Adobe illustrator 案例二:矢量仪表盘图标绘制

Adobe illustrator 案例二:矢量仪表盘图标绘制

完成版第一阶段:新建文档与绘图环境配置步骤 1:新建画布与文档设置新建文档:打开 Illustrator,点击左侧菜单栏的 “新建文件” 按钮。选择预设与尺寸:在弹出的新建文档窗口中,切换至 “打印” 标签页&#…

2026/11/20 15:04:10 阅读更多 →
月球遥感——氦-3的反演理论发展历程

月球遥感——氦-3的反演理论发展历程

目录 总框架:光谱反演深度积分模块一:月球表面3He丰度 C₀ 太阳风强度计算:月壤成熟度计算:TiO2 含量计算: 模块二:月壤剖面3He丰度变化函数 f(z)模块三:月壤厚度 d总结 总框架:光…

2026/11/15 3:30:41 阅读更多 →
免搭建数据库!用几行 Python 代码打造轻量级自选股实时监控系统

免搭建数据库!用几行 Python 代码打造轻量级自选股实时监控系统

📌 摘要 / 快速解答 (Direct Answer) 构建自选股实时监控系统并不需要搭建复杂的 InfluxDB 或 MySQL 数据库,也不需要编写易被封禁的爬虫。通过开源 QuantDash Python SDK,只需几行 Python 代码即可调用服务端统一清洗好的 A股/美股/港股实时…

2026/11/17 5:39:37 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻