新闻详情

新闻详情

首页 / 资讯中心 / 详情

Learn-Algorithms 笔记:AVL 自平衡二叉查找树——从平衡因子到四种旋转的完整解析

发布时间:2026/11/17 4:04:08来源:尧图网络
Learn-Algorithms 笔记:AVL 自平衡二叉查找树——从平衡因子到四种旋转的完整解析
教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载AVL 树Adelson-Velskii and Landis Tree是最早被发明的自平衡二叉查找树它保证任意节点的左右子树高度差不超过 1从而让查找、插入、删除在平均和最坏情况下都维持在 O(logn)。本文以仓库 4 Tree/3-平衡树AVL/README.md 为核心骨架结合同目录的 AVLTree.c 源码与 二叉查找树、红黑树 笔记系统讲解平衡因子、LL/RR/LR/RL 四种旋转、插入与删除流程以及 AVL 树的适用场景与工程取舍读完即可在笔试面试与编码中正确实现并权衡选用 AVL 树。1. 什么是 AVL 树严格平衡的二叉查找树自平衡二叉查找树AVL tree首先是一棵二叉查找树Binary Search Tree, BST即满足“左小右大”的排序性质任意节点的左子树所有值小于根值右子树所有值大于根值中序遍历结果严格递增。在此基础上AVL 树额外追加一条严格平衡约束任何节点的左右子树的高度差不大于 1。正是这条约束保证了 AVL 树的高度始终接近 log₂n使查找操作在平均和最坏情况下都是 O(logn)。而在删除、插入的过程中AVL 树会不断调整子树的高度以维持该约束这是它与普通 BST 的本质区别。AVL 树由苏联数学家 Adelson-Velskii 和 Landis 于1962 年创造因此命名为 AVL 树取自两人姓氏首字母。它也是历史上第一个被提出的自平衡二叉查找树。1.1 平衡因子Balance FactorAVL 树引入了一个核心度量指标——平衡因子平衡因子 左子树高度 - 右子树高度平衡因子为-1、0、1的节点是正常的符合 AVL 平衡约束除此之外即平衡因子达到±2的节点是不平衡的需要重新平衡这棵子树也就是执行 AVL 旋转。仓库源码 AVLTree.c 用宏直接定义了三种平衡状态#define LH 1 // 左高左子树比右子树高 1 #define EH 0 // 等高左右子树高度相同 #define RH -1 // 右高右子树比左子树高 1节点结构体则在 key 之外专门保存一个height字段注释中标为“平衡因子”typedef int KEY_TYPE; typedef struct node{ KEY_TYPE key; int height; // 平衡因子 struct node *lChild; struct node *rChild; } AVLTree;1.2 实际使用案例原文档给出了两个可查证的实际应用方向LLVM 的 ImmutableSet其底层实现选择 AVL 树作为不可变集合的容器结构P2P 覆盖网络研究论文《一种基于二叉平衡树的 P2P 覆盖网络的研究》利用 AVL 树的平衡特性组织覆盖网络节点。这两个案例都指向 AVL 树的典型定位读多写少、对树高度敏感的场景。2. 插入节点四种旋转一次讲清向 AVL 树插入新节点后可能破坏某个祖先节点的平衡平衡因子由 ±1 变为 ±2此时需要按“插入位置”分类执行单旋转或双旋转。原文档归纳为四类a. 左旋转RR 型在节点 x 的右孩子的右孩子上插入新元素平衡因子由 -1 变为 -2 时绕节点 x 做一次左旋转b. 右旋转LL 型在节点 x 的左孩子的左孩子上插入新元素平衡因子由 1 变为 2 时绕 x 做一次右旋转c. 先左后右旋转LR 型在节点 x 的左孩子的右孩子上插入新元素平衡因子由 1 变成 2 后先绕 x 的左子节点 Y 做左旋转再绕 x 做右旋转d. 先右后左旋转RL 型在节点 x 的右孩子的左孩子上插入新元素先绕 x 的右子节点做右旋转再绕 x 做左旋转。原文档用一棵树形图直观给出了四种失衡形态6 6 6 6 / \ / \ 5 7 3 9 / \ \ / 3 8 5 7 (LL型) (RR) (LR) (RL)判型的关键口诀是看“插入位置相对于失衡节点 x 的孙子节点方向”——左-左走 LL 单右旋右-右走 RR 单左旋左-右走 LR 双旋先左后右右-左走 RL 双旋先右后左。2.1 源码中的旋转与平衡处理仓库 AVLTree.c 保留了旋转函数与平衡函数的雏形注该文件是笔记性源码片段个别实现不完整阅读时需结合标准 AVL 算法理解其意图avltree_ll_rotate左-左型单右旋把左孩子提升为根avltree_rr_rotate右-右型单左旋把右孩子提升为根avltree_lr_rotate/avltree_rl_rotate双旋入口avltree_left_balance检查左子树平衡度并作相应平衡处理——当左孩子平衡因子为LH新节点插入左孩子的左子树时做单右旋当为RH新节点插入左孩子的右子树时做双旋处理并根据lr-height的 LH/EH/RH 三种取值分别修正根、左孩子与lr的平衡因子最后执行“先对左孩子左旋、再对根右旋”avltree_right_balance对称地处理右侧失衡——RH时单左旋LH时“先对右孩子右旋、再对根左旋”。avltree_insert则给出了递归插入的主流程骨架根为空则创建新节点分配失败时打印“内存分配失败”key 已存在则不重复插入key 小于根则插入左子树插入后比较左右子树高度差是否为 2再依据新 key 与左孩子 key 的大小关系区分 LL 型右旋与 LR 型双旋key 大于根则对称处理右子树的 RL 与 RR 型。这与原文档中“插入后检查平衡因子、按四型旋转”的描述完全对应。2.2 测试用例插入建树与中序遍历验证main函数给出了可直接验证的测试思路AVLTree.cint values[] {11, 7, 222, 456, 23, 8, 65, 124, 88, 2, 54}; for (int i 0; i sizeof(values)/sizeof(int); i) { avlTree avltree_insert(avlTree, values[i]); avltree_inorder_traversal(avlTree); }每插入一个节点就做一次中序遍历——因为 AVL 树首先是 BST中序遍历结果必须是递增序列这是验证“排序性质未被旋转破坏”的最直接手段配合avltree_isbalance检查高度差即可验证“平衡约束被恢复”。测试还覆盖了删除存在的节点、删除不存在的节点应安全返回、查找存在与不存在的节点等边界场景。3. 删除节点代价高于插入AVL 树的删除流程为先按 BST 规则找到并删除目标节点叶子直接删除只有一个分支则用其孩子顶替有两个分支则用左子树最大节点或右子树最小节点替换与 二叉查找树 中的删除思路一致然后从被删节点的祖先开始逐层向上检查平衡因子一旦发现 |平衡因子| 2就按插入同样的 LL/RR/LR/RL 规则旋转修复并继续向上回溯直到根节点。原文档明确指出为了保证高度平衡插入和删除操作的代价会增加。相比普通 BST删除后的平衡修复可能需要沿路径多次旋转这也是 AVL 树“写操作贵”的根源。仓库中的avltree_delete仅保留了函数签名AVLTree.c实现需读者按上述流程补全。4. 实现中的问题严格平衡的代价与红黑树之选4.1 旋转开销大适合“读多写少”AVL 是严格的平衡二叉树平衡条件必须满足即所有节点的左右子树高度差的绝对值不超过 1。无论执行插入还是删除操作只要不满足条件就要通过旋转保持平衡而旋转是非常耗时的。由此可以得出清晰的工程结论AVL 树适合用于插入与删除次数比较少、但查找多的情况。因为查找只依赖树高AVL 树是自平衡 BST 中高度最矮最接近 log₂n的一种读操作能拿到最优上界而写操作因频繁旋转付出额外代价。4.2 为什么实际中更多用红黑树原文档给出了一个重要判断由于维护这种高度平衡所付出的代价比从中获得的效率收益还大AVL 树实际应用不多更多的地方使用的是追求局部平衡而非严格整体平衡的红黑树。这与仓库 红黑树 笔记相互印证红黑树是弱平衡二叉树只保证“没有任何一条路径会比其它路径长出两倍”在相同节点数下AVL 树的高度低于红黑树红黑树牺牲了一定的平衡性即牺牲部分查找性能换来插入、删除时更少的旋转次数带来的开销因此对搜索、插入、删除操作都较多的场景通常选用红黑树如 C STL 的 map/set、Java TreeMap、Linux 进程与内存管理、epoll 的 sockfd 管理、Nginx 的定时器管理等而 AVL 树凭借更严格的高度保证仍适合查找密集的场景。从更宏观的选型看仓库笔记还指出红黑树多用于内部排序数据全放内存而 B 树多用于外存磁盘友好这也是 MySQL 索引选择 B 树而非红黑树的原因。5. 小结AVL 树用“平衡因子 ±1”的严格约束换来了 O(logn) 的确定性查找上界代价是插入、删除时的旋转开销。理解 LL/RR/LR/RL 四种旋转形态与左/右平衡函数是掌握 AVL 树实现的关键而“何时用 AVL、何时用红黑树”的取舍则要看业务是读密集还是写密集。本文对应的完整笔记与源码分别位于 README.md 与 AVLTree.c可与 二叉查找树、红黑树 及 树模块总览 一起串读形成从 BST 到 AVL、再到红黑树的完整平衡树知识链。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Swift Algorithm Club 深度解析AVL 自平衡二叉搜索树AVL Tree的平衡因子、旋转与源码实现Swift Algorithm Club 深度解析AVL 自平衡二叉搜索树AVL Tree的平衡因子、旋转与源码实现 AVL 树是第一种被提出的自平衡二叉示例工程教程电视盒子改造终极指南三步把闲置 Amlogic 盒子变成 Armbian 服务器电视盒子改造终极指南三步把闲置 Amlogic 盒子变成 Armbian 服务器 家里吃灰的电视盒子只能当摆设吗想把它变成能跑 Docker、挂服务的 Li嵌入式开发工具构建工具操作系统Hello 算法AVL 树自平衡二叉搜索树详解——从旋转到增删查的完整实现剖析Hello 算法AVL 树自平衡二叉搜索树详解——从旋转到增删查的完整实现剖析 本篇以《Hello 算法》日文版 AVL 木章节 https://link教程文档示例工程教育上一篇解锁VMware macOS支持解决虚拟机系统限制的完整技术指南下一篇用 C 扩展定制 PyTorch 分布式集体通信后端ProcessGroup Backend 插件化开发全流程创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉