教程【免费下载链接】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），仅供参考