小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、AVL 树核心概念什么是 “高度平衡”二、 AVL 树结构设计节点与类定义三、AVL 树插入从 BST 插入到旋转实现平衡修正1、平衡因子更新原则2、平衡因子更新关键逻辑四. AVL 树旋转失衡恢复的四种方式1、右单旋RotateR左子树过高父 BF-2子 BF-11.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 11.3 情况3插入前a / b / c高度h 21.4 情况4插入前a / b / c高度h 3代码实现注意看注释代码与图示联系理解2、左单旋RotateL右子树过高父 BF2子 BF1代码实现注意看注释3、左右双旋RotateLR左子树的右子树过高父 BF-2子 BF11.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 1代码实现注意看注释4、右左双旋RotateRL右子树的左子树过高父 BF2子 BF-1代码实现注意看注释五、AVL树的平衡检查验证树的正确性测试代码示例结束语前言在二叉搜索树BST中若插入顺序有序如递增或递减树会退化为链表导致增删查效率从O(logN) 骤降至 O(N)。为解决这一问题AVL 树自平衡二叉搜索树应运而生 —— 它通过控制左右子树的高度差平衡因子确保树始终保持 “高度平衡”从而稳定维持O(logN)的高效操作。本文将从 AVL 树的核心概念切入结合完整代码实现详解插入逻辑、平衡因子更新与四种旋转操作。本篇文章的AVL树代码实现总览代码仓库C STL AVL树实现一、AVL 树核心概念什么是 “高度平衡”AVL 树是一种特殊的二叉搜索树满足两个核心条件二叉搜索树特性左子树所有节点值 根节点值 右子树所有节点值高度平衡特性任意节点的左右子树高度差的绝对值 ≤ 1。为了更直观判断平衡状态引入了平衡因子balance factor平衡因子 右子树高度 - 左子树高度AVL 树中任意节点的平衡因子只能是 -1、0、1若平衡因子为 2 或 -2说明树已失衡需通过 “旋转” 恢复平衡。思考为什么不要求平衡因子为 0某些场景下如 2 个节点、4 个节点树无法做到左右子树高度完全相等如根节点左子树高 1右子树高 0此时平衡因子为 1仍满足 “高度差≤1” 的平衡要求。二、 AVL 树结构设计节点与类定义AVL 树的节点需存储键值对、左右孩子指针、父指针用于往上查找父亲结点来更新平衡因子和平衡因子。类定义如下#include iostream #include assert.h using namespace std; // AVL树节点的结构 templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _father;// 父节点指针后续更新平衡因子要用到 int _bf; //balance factor(平衡因子) AVLTreeNode(const pairK, V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) , _father(nullptr) ,_bf(0) { } }; // AVL树类 templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: // 插入、旋转等核心接口下文会详细解析 bool Insert(const pairK, V kv); void RotateR(Node* father); // 右单旋 void RotateL(Node* father); // 左单旋 void RotateLR(Node* father); // 左右双旋 void RotateRL(Node* father); // 右左双旋 private: Node* _root nullptr; };三、AVL 树插入从 BST 插入到旋转实现平衡修正AVL 树的插入流程分为两步按 BST 规则插入节点 → 回溯更新平衡因子失衡则旋转恢复。这是 AVL 树维持平衡的核心环节需重点理解平衡因子的更新逻辑与停止条件。1、平衡因子更新原则平衡因子 右子树高度 - 左子树高度只有子树高度变化才会影响当前结点平衡因子插入结点会增加高度所以新增结点在 parent 的右子树parent 的平衡因子新增结点在 parent 的左子树parent 平衡因子--(后续更新平衡因子的关键条件)parent 所在子树的高度是否变化决定了是否会继续往上更新2、平衡因子更新关键逻辑更新平衡因子时核心是判断“当前子树高度是否变化”进而决定是否继续向上更新BF 0插入前父节点子树 “有一侧高 1”如 BF 1 或 - 1插入后两侧平衡高度不变 →停止更新BF 1 / -1插入前父节点子树 “平衡”BF 0插入后“有一侧高1”高度 1 →继续更新BF 2 / -2插入前父节点子树 “有一侧高 1”插入后“有一侧高 2”失衡→旋转后停止更新。更新到根根的平衡因子是 1 或 -1 也停止。下面有几个情况图示来展示插入结点后平衡因子的更新(1)更新到中间结点3为根的子树高度不变不会影响上一层更新结束(2)更新到 10 结点平衡因子为210所在的子树已经不平衡需要旋转处理(3)最坏情况更新到根为止四. AVL 树旋转失衡恢复的四种方式当节点平衡因子为 2 或 - 2 时需通过 “旋转” 恢复平衡。旋转的核心目标有两个维持二叉搜索树特性 降低失衡子树高度。根据失衡形态分为四种旋转方式1、右单旋RotateR左子树过高父 BF-2子 BF-1下图中展现的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根。这里a/b/c是高度为h的子树是一种概括抽象的表示他代表了所有右单旋的场景但实际右单旋的场景很多大家可以看看后面的实际场景图。在 a 子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树的左边太高了需要往右边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的左子树subL和 subL 的右子树subLR将 subLR 作为 parent 的左子树若 subLR 非空更新其 parent 指针将 parent 作为 subL 的右子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subL 与祖父节点若 parent 是根节点更新_root重置 parent 和 subL 的平衡因子为 0。下面展示了具体四种情况演示只是作为参考比较抽象具象图画不完的但是抽象图可以很好地代表具象图具象图也是这个逻辑大家作为参考就好了1.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 11.3 情况3插入前a / b / c高度h 21.4 情况4插入前a / b / c高度h 3代码实现注意看注释public: void RotateR(Node* father) { Node* subL father-_left; Node* subLR subL-_right; //需要注意subLR可能为空 Node* prev_father father-_father; father-_left subLR; if (subLR) { //如果subLR为空树则subLR没有_father指向father结点 subLR-_father father; } subL-_right father; father-_father subL; if (father _root) { //如果原来失衡结点就是根节点则旋转后subL就是根节点 //需要注意原根节点没有_father而subL有需要将_root的_father置空 _root subL; _root-_father nullptr; } else { //如果原来失衡结点是某个子树则需要重新与上一个结点进行链接 //链接前还需要判断原father是在上一个结点prev_father的左边还是右边 if (prev_father-_left father) { prev_father-_left subL; } else { prev_father-_right subL; } subL-_father prev_father; } //最后将father和subL结点的平衡因子更新一下 father-_bf subL-_bf 0; }代码与图示联系理解2、左单旋RotateL右子树过高父 BF2子 BF1下图中展示的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根也可能是一整颗树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示他代表所有左单旋的场景实际左单旋场景有很多具体跟上面的右旋类似。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了。需要往左边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的右子树subR和 subR 的左子树subRL将 subRL 作为 parent 的右子树若 subRL 非空更新其 parent 指针将 parent 作为 subR 的左子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subR 与祖父节点或更新_root重置 parent 和 subR 的平衡因子为 0。由于右单旋的逻辑和左单旋非常类似就不再展示右单选的每种情况例子图示了。代码实现注意看注释public: void RotateL(Node* father) { Node* subR father-_right; Node* subRL subR-_left;//需要注意subRL可能为空 Node* prev_father father-_father; father-_right subRL; if (subRL) { //如果subRL为空树则subRL没有_father指向father结点 subRL-_father father; } subR-_left father; father-_father subR; if (father _root) { // 如果原来失衡结点就是根节点则旋转后subR就是根节点 // 需要注意原根节点没有_father而subR有需要将_root的_father置空 _root subR; _root-_father nullptr; } else { // 如果原来失衡结点是某个子树则需要重新与上一个结点进行链接 // 链接前还需要判断原father是在上一个结点prev_father的左边还是右边 if (prev_father-_left father) { prev_father-_left subR; } else { prev_father-_right subR; } subR-_father prev_father; } //最后将father和sunR结点的平衡因子更新一下 father-_bf subR-_bf 0; }3、左右双旋RotateLR左子树的右子树过高父 BF-2子 BF1通过下面情况1和情况2的两张图我们可以观察到当左边高时如果插入位置不是在a子树而是插入在b子树b子树高度从h变成h 1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边高但是插入在b子树中10为跟的子树不再是单纯的左边高对于10是左边高但是对于5是右边高需要用两次旋转才能解决——以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这棵树就平衡了。1.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 1上面两张图分别为左右双旋中h 0和h 1两种情况的具体场景的流程分析下面我们将a / b / c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为8和左子树高度为h -1的e和f子树因为我们要以b的父亲节点5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。旋转核心步骤对父节点的左子树subL执行左单旋将 subL 的右子树 subLR 提升为 subL 的父节点对父节点parent执行右单旋将修正后的 subL 提升为 parent 的父节点根据 subLR 的原始平衡因子重置三个节点parent、subL、subLR的平衡因子三种场景场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新 subLR-subL-parent 平衡因子引发旋转其中subLR的平衡因子为 -1旋转后subLR和subL平衡因子为0parent的平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新 subLR-subL-parent 平衡因子引发旋转其中subLR的平衡因子为1旋转后subLR和parent的平衡因子为0subL的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新 subL-parent 平衡因子引发旋转其中subLR的平衡因子为0旋转后subLR,subL和parent的平衡因子都为0。场景1场景2场景3前两个场景我们可以得到一个技巧性的旋转结果思路前两个场景的通用图例代码实现注意看注释public: void RotateLR(Node* father) { Node* subL father-_left;// father的左子树 Node* subLR subL-_right;// subL的右子树关键节点决定平衡因子重置 int bf subLR-_bf;// 记录 subLR 的原始bf用于后续判断是旋转的哪个场景 // 步骤1先对subL执行左单旋修正左子树的失衡 RotateL(subL); // 步骤2再对father执行右单旋修正父节点的失衡 RotateR(father); // 步骤3根据subLR的原始bf重置三个节点的平衡因子 if (bf -1) { // 场景1subLR的左子树高bf -1→ father的右子树高subL的左子树高 subL-_bf 0; subLR-_bf 0; father-_bf 1; } else if(bf 1) { // 场景2subLR的右子树高bf 1→ father的左子树高subL的右子树高 subL-_bf -1; subLR-_bf 0; father-_bf 0; } else if(bf 0) { // 场景3subLR是新插入节点bf 0→ 旋转后三者bf均为0 subL-_bf 0; subLR-_bf 0; father-_bf 0; } else { //异常情况 assert(false); } }4、右左双旋RotateRL右子树的左子树过高父 BF2子 BF-1跟左右双旋类似下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同不同这里我们要分三个场景讨论。旋转核心步骤对父节点的右子树subR执行右单旋对父节点parent执行左单旋根据 subRL 的原始平衡因子重置三个节点的平衡因子。场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新subRL-subR-parent 平衡因子引发旋转其中subRL的平衡因子为-1旋转后parent和subRL平衡因子为0subR平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新subRL-subR-parent 平衡因子,引发旋转其中subRL的平衡因子为1旋转后subR和subRL的平衡因子为0parent的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新 subR-parent 平衡因子引发旋转其中subRL的平衡因子为0旋转后三者的平衡因子都是0。代码实现注意看注释public: void RotateRL(Node* father) { Node* subR father-_right;// father的左子树 Node* subRL subR-_left;// subL的右子树关键节点决定平衡因子重置 int bf subRL-_bf;// 记录 subLR 的原始bf用于后续判断是旋转的哪个场景 // 步骤1先对subL执行左单旋修正左子树的失衡 RotateR(subR); // 步骤2再对father执行右单旋修正父节点的失衡 RotateL(father); // 步骤3根据subLR的原始bf重置三个节点的平衡因子 if (bf -1) { // 场景1subLR的左子树高bf -1→ father的右子树高subL的左子树高 subR-_bf 1; subRL-_bf 0; father-_bf 0; } else if (bf 1) { // 场景2subLR的右子树高bf 1→ father的左子树高subL的右子树高 subR-_bf 0; subRL-_bf 0; father-_bf -1; } else if (bf 0) { // 场景3subLR是新插入节点bf 0→ 旋转后三者bf均为0 subR-_bf 0; subRL-_bf 0; father-_bf 0; } else { //异常情况 assert(false); } }五、AVL树的平衡检查验证树的正确性public: // 对外接口验证AVL树 bool IsBalanceTree() { return _IsBalanceTree(_root); } //AVL树平衡检测 int _Height(Node * root) { if (root nullptr) return 0; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; } bool _IsBalanceTree(Node * root) { // 空树也是AVL树 if (nullptr root) return true; // 计算pRoot结点的平衡因⼦即pRoot左右⼦树的⾼度差 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等或者 // pRoot平衡因⼦的绝对值超过1则⼀定不是AVL树 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } // pRoot的左和右如果都是AVL树则该树⼀定是AVL树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } //中序遍历 void Print() { _Print(_root); } private: void _Print(const Node* root) { if (root nullptr) { return; } _Print(root-_left); cout root-_kv.first : root-_kv.second endl; _Print(root-_right); }测试代码示例#includeAVLTree.h void test_RotateR() { AVLTreeint, int tree; tree.Insert({ 5, 50 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 2, 20 }); tree.Insert({ 4, 40 }); tree.Insert({ 1, 10 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateL() { AVLTreeint, int tree; tree.Insert({ 5, 50 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 6, 60 }); tree.Insert({ 8, 80 }); tree.Insert({ 9, 90 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateLR() { AVLTreeint, int tree; tree.Insert({ 6, 60 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 2, 20 }); tree.Insert({ 4, 40 }); tree.Insert({ 5, 50 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateRL() { AVLTreeint, int tree; tree.Insert({ 6, 60 }); tree.Insert({ 3, 30 }); tree.Insert({ 9, 90 }); tree.Insert({ 7, 70 }); tree.Insert({ 4, 40 }); tree.Insert({ 8, 80 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } int main() { test_RotateR(); test_RotateL(); test_RotateLR(); test_RotateRL(); return 0; }tree.IsBalanceTree() 输出为 1 就能证明我们成功实现了 AVL树 的平衡如果不为1也能说明我们自己所实现的旋转代码或者插入代码出现了问题便于我们发现。结束语到此C AVL树的实现就讲解完了。AVL 树以 “平衡因子” 控平衡、“旋转操作” 修失衡将增删查效率稳定在(O(log N))是自平衡树的经典范式。其核心魅力在于用简洁的平衡逻辑高度差≤1和精准的旋转策略解决了不同场景下的失衡情况化解普通二叉搜索树退化的问题虽高频写场景下旋转开销略逊于红黑树但对平衡原理的直观呈现使其成为理解复杂自平衡结构的基石。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/
【C++：AVL树】平衡核心、旋转策略：从原理到完整代码实现
发布时间：2026/7/18 5:16:35
小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、AVL 树核心概念什么是 “高度平衡”二、 AVL 树结构设计节点与类定义三、AVL 树插入从 BST 插入到旋转实现平衡修正1、平衡因子更新原则2、平衡因子更新关键逻辑四. AVL 树旋转失衡恢复的四种方式1、右单旋RotateR左子树过高父 BF-2子 BF-11.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 11.3 情况3插入前a / b / c高度h 21.4 情况4插入前a / b / c高度h 3代码实现注意看注释代码与图示联系理解2、左单旋RotateL右子树过高父 BF2子 BF1代码实现注意看注释3、左右双旋RotateLR左子树的右子树过高父 BF-2子 BF11.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 1代码实现注意看注释4、右左双旋RotateRL右子树的左子树过高父 BF2子 BF-1代码实现注意看注释五、AVL树的平衡检查验证树的正确性测试代码示例结束语前言在二叉搜索树BST中若插入顺序有序如递增或递减树会退化为链表导致增删查效率从O(logN) 骤降至 O(N)。为解决这一问题AVL 树自平衡二叉搜索树应运而生 —— 它通过控制左右子树的高度差平衡因子确保树始终保持 “高度平衡”从而稳定维持O(logN)的高效操作。本文将从 AVL 树的核心概念切入结合完整代码实现详解插入逻辑、平衡因子更新与四种旋转操作。本篇文章的AVL树代码实现总览代码仓库C STL AVL树实现一、AVL 树核心概念什么是 “高度平衡”AVL 树是一种特殊的二叉搜索树满足两个核心条件二叉搜索树特性左子树所有节点值 根节点值 右子树所有节点值高度平衡特性任意节点的左右子树高度差的绝对值 ≤ 1。为了更直观判断平衡状态引入了平衡因子balance factor平衡因子 右子树高度 - 左子树高度AVL 树中任意节点的平衡因子只能是 -1、0、1若平衡因子为 2 或 -2说明树已失衡需通过 “旋转” 恢复平衡。思考为什么不要求平衡因子为 0某些场景下如 2 个节点、4 个节点树无法做到左右子树高度完全相等如根节点左子树高 1右子树高 0此时平衡因子为 1仍满足 “高度差≤1” 的平衡要求。二、 AVL 树结构设计节点与类定义AVL 树的节点需存储键值对、左右孩子指针、父指针用于往上查找父亲结点来更新平衡因子和平衡因子。类定义如下#include iostream #include assert.h using namespace std; // AVL树节点的结构 templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _father;// 父节点指针后续更新平衡因子要用到 int _bf; //balance factor(平衡因子) AVLTreeNode(const pairK, V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) , _father(nullptr) ,_bf(0) { } }; // AVL树类 templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: // 插入、旋转等核心接口下文会详细解析 bool Insert(const pairK, V kv); void RotateR(Node* father); // 右单旋 void RotateL(Node* father); // 左单旋 void RotateLR(Node* father); // 左右双旋 void RotateRL(Node* father); // 右左双旋 private: Node* _root nullptr; };三、AVL 树插入从 BST 插入到旋转实现平衡修正AVL 树的插入流程分为两步按 BST 规则插入节点 → 回溯更新平衡因子失衡则旋转恢复。这是 AVL 树维持平衡的核心环节需重点理解平衡因子的更新逻辑与停止条件。1、平衡因子更新原则平衡因子 右子树高度 - 左子树高度只有子树高度变化才会影响当前结点平衡因子插入结点会增加高度所以新增结点在 parent 的右子树parent 的平衡因子新增结点在 parent 的左子树parent 平衡因子--(后续更新平衡因子的关键条件)parent 所在子树的高度是否变化决定了是否会继续往上更新2、平衡因子更新关键逻辑更新平衡因子时核心是判断“当前子树高度是否变化”进而决定是否继续向上更新BF 0插入前父节点子树 “有一侧高 1”如 BF 1 或 - 1插入后两侧平衡高度不变 →停止更新BF 1 / -1插入前父节点子树 “平衡”BF 0插入后“有一侧高1”高度 1 →继续更新BF 2 / -2插入前父节点子树 “有一侧高 1”插入后“有一侧高 2”失衡→旋转后停止更新。更新到根根的平衡因子是 1 或 -1 也停止。下面有几个情况图示来展示插入结点后平衡因子的更新(1)更新到中间结点3为根的子树高度不变不会影响上一层更新结束(2)更新到 10 结点平衡因子为210所在的子树已经不平衡需要旋转处理(3)最坏情况更新到根为止四. AVL 树旋转失衡恢复的四种方式当节点平衡因子为 2 或 - 2 时需通过 “旋转” 恢复平衡。旋转的核心目标有两个维持二叉搜索树特性 降低失衡子树高度。根据失衡形态分为四种旋转方式1、右单旋RotateR左子树过高父 BF-2子 BF-1下图中展现的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根。这里a/b/c是高度为h的子树是一种概括抽象的表示他代表了所有右单旋的场景但实际右单旋的场景很多大家可以看看后面的实际场景图。在 a 子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树的左边太高了需要往右边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的左子树subL和 subL 的右子树subLR将 subLR 作为 parent 的左子树若 subLR 非空更新其 parent 指针将 parent 作为 subL 的右子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subL 与祖父节点若 parent 是根节点更新_root重置 parent 和 subL 的平衡因子为 0。下面展示了具体四种情况演示只是作为参考比较抽象具象图画不完的但是抽象图可以很好地代表具象图具象图也是这个逻辑大家作为参考就好了1.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 11.3 情况3插入前a / b / c高度h 21.4 情况4插入前a / b / c高度h 3代码实现注意看注释public: void RotateR(Node* father) { Node* subL father-_left; Node* subLR subL-_right; //需要注意subLR可能为空 Node* prev_father father-_father; father-_left subLR; if (subLR) { //如果subLR为空树则subLR没有_father指向father结点 subLR-_father father; } subL-_right father; father-_father subL; if (father _root) { //如果原来失衡结点就是根节点则旋转后subL就是根节点 //需要注意原根节点没有_father而subL有需要将_root的_father置空 _root subL; _root-_father nullptr; } else { //如果原来失衡结点是某个子树则需要重新与上一个结点进行链接 //链接前还需要判断原father是在上一个结点prev_father的左边还是右边 if (prev_father-_left father) { prev_father-_left subL; } else { prev_father-_right subL; } subL-_father prev_father; } //最后将father和subL结点的平衡因子更新一下 father-_bf subL-_bf 0; }代码与图示联系理解2、左单旋RotateL右子树过高父 BF2子 BF1下图中展示的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根也可能是一整颗树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示他代表所有左单旋的场景实际左单旋场景有很多具体跟上面的右旋类似。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了。需要往左边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的右子树subR和 subR 的左子树subRL将 subRL 作为 parent 的右子树若 subRL 非空更新其 parent 指针将 parent 作为 subR 的左子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subR 与祖父节点或更新_root重置 parent 和 subR 的平衡因子为 0。由于右单旋的逻辑和左单旋非常类似就不再展示右单选的每种情况例子图示了。代码实现注意看注释public: void RotateL(Node* father) { Node* subR father-_right; Node* subRL subR-_left;//需要注意subRL可能为空 Node* prev_father father-_father; father-_right subRL; if (subRL) { //如果subRL为空树则subRL没有_father指向father结点 subRL-_father father; } subR-_left father; father-_father subR; if (father _root) { // 如果原来失衡结点就是根节点则旋转后subR就是根节点 // 需要注意原根节点没有_father而subR有需要将_root的_father置空 _root subR; _root-_father nullptr; } else { // 如果原来失衡结点是某个子树则需要重新与上一个结点进行链接 // 链接前还需要判断原father是在上一个结点prev_father的左边还是右边 if (prev_father-_left father) { prev_father-_left subR; } else { prev_father-_right subR; } subR-_father prev_father; } //最后将father和sunR结点的平衡因子更新一下 father-_bf subR-_bf 0; }3、左右双旋RotateLR左子树的右子树过高父 BF-2子 BF1通过下面情况1和情况2的两张图我们可以观察到当左边高时如果插入位置不是在a子树而是插入在b子树b子树高度从h变成h 1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边高但是插入在b子树中10为跟的子树不再是单纯的左边高对于10是左边高但是对于5是右边高需要用两次旋转才能解决——以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这棵树就平衡了。1.1 情况1插入前a / b / c高度h 01.2 情况2插入前a / b / c高度h 1上面两张图分别为左右双旋中h 0和h 1两种情况的具体场景的流程分析下面我们将a / b / c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为8和左子树高度为h -1的e和f子树因为我们要以b的父亲节点5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。旋转核心步骤对父节点的左子树subL执行左单旋将 subL 的右子树 subLR 提升为 subL 的父节点对父节点parent执行右单旋将修正后的 subL 提升为 parent 的父节点根据 subLR 的原始平衡因子重置三个节点parent、subL、subLR的平衡因子三种场景场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新 subLR-subL-parent 平衡因子引发旋转其中subLR的平衡因子为 -1旋转后subLR和subL平衡因子为0parent的平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新 subLR-subL-parent 平衡因子引发旋转其中subLR的平衡因子为1旋转后subLR和parent的平衡因子为0subL的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新 subL-parent 平衡因子引发旋转其中subLR的平衡因子为0旋转后subLR,subL和parent的平衡因子都为0。场景1场景2场景3前两个场景我们可以得到一个技巧性的旋转结果思路前两个场景的通用图例代码实现注意看注释public: void RotateLR(Node* father) { Node* subL father-_left;// father的左子树 Node* subLR subL-_right;// subL的右子树关键节点决定平衡因子重置 int bf subLR-_bf;// 记录 subLR 的原始bf用于后续判断是旋转的哪个场景 // 步骤1先对subL执行左单旋修正左子树的失衡 RotateL(subL); // 步骤2再对father执行右单旋修正父节点的失衡 RotateR(father); // 步骤3根据subLR的原始bf重置三个节点的平衡因子 if (bf -1) { // 场景1subLR的左子树高bf -1→ father的右子树高subL的左子树高 subL-_bf 0; subLR-_bf 0; father-_bf 1; } else if(bf 1) { // 场景2subLR的右子树高bf 1→ father的左子树高subL的右子树高 subL-_bf -1; subLR-_bf 0; father-_bf 0; } else if(bf 0) { // 场景3subLR是新插入节点bf 0→ 旋转后三者bf均为0 subL-_bf 0; subLR-_bf 0; father-_bf 0; } else { //异常情况 assert(false); } }4、右左双旋RotateRL右子树的左子树过高父 BF2子 BF-1跟左右双旋类似下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同不同这里我们要分三个场景讨论。旋转核心步骤对父节点的右子树subR执行右单旋对父节点parent执行左单旋根据 subRL 的原始平衡因子重置三个节点的平衡因子。场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新subRL-subR-parent 平衡因子引发旋转其中subRL的平衡因子为-1旋转后parent和subRL平衡因子为0subR平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新subRL-subR-parent 平衡因子,引发旋转其中subRL的平衡因子为1旋转后subR和subRL的平衡因子为0parent的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新 subR-parent 平衡因子引发旋转其中subRL的平衡因子为0旋转后三者的平衡因子都是0。代码实现注意看注释public: void RotateRL(Node* father) { Node* subR father-_right;// father的左子树 Node* subRL subR-_left;// subL的右子树关键节点决定平衡因子重置 int bf subRL-_bf;// 记录 subLR 的原始bf用于后续判断是旋转的哪个场景 // 步骤1先对subL执行左单旋修正左子树的失衡 RotateR(subR); // 步骤2再对father执行右单旋修正父节点的失衡 RotateL(father); // 步骤3根据subLR的原始bf重置三个节点的平衡因子 if (bf -1) { // 场景1subLR的左子树高bf -1→ father的右子树高subL的左子树高 subR-_bf 1; subRL-_bf 0; father-_bf 0; } else if (bf 1) { // 场景2subLR的右子树高bf 1→ father的左子树高subL的右子树高 subR-_bf 0; subRL-_bf 0; father-_bf -1; } else if (bf 0) { // 场景3subLR是新插入节点bf 0→ 旋转后三者bf均为0 subR-_bf 0; subRL-_bf 0; father-_bf 0; } else { //异常情况 assert(false); } }五、AVL树的平衡检查验证树的正确性public: // 对外接口验证AVL树 bool IsBalanceTree() { return _IsBalanceTree(_root); } //AVL树平衡检测 int _Height(Node * root) { if (root nullptr) return 0; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; } bool _IsBalanceTree(Node * root) { // 空树也是AVL树 if (nullptr root) return true; // 计算pRoot结点的平衡因⼦即pRoot左右⼦树的⾼度差 int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等或者 // pRoot平衡因⼦的绝对值超过1则⼀定不是AVL树 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } // pRoot的左和右如果都是AVL树则该树⼀定是AVL树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } //中序遍历 void Print() { _Print(_root); } private: void _Print(const Node* root) { if (root nullptr) { return; } _Print(root-_left); cout root-_kv.first : root-_kv.second endl; _Print(root-_right); }测试代码示例#includeAVLTree.h void test_RotateR() { AVLTreeint, int tree; tree.Insert({ 5, 50 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 2, 20 }); tree.Insert({ 4, 40 }); tree.Insert({ 1, 10 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateL() { AVLTreeint, int tree; tree.Insert({ 5, 50 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 6, 60 }); tree.Insert({ 8, 80 }); tree.Insert({ 9, 90 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateLR() { AVLTreeint, int tree; tree.Insert({ 6, 60 }); tree.Insert({ 3, 30 }); tree.Insert({ 7, 70 }); tree.Insert({ 2, 20 }); tree.Insert({ 4, 40 }); tree.Insert({ 5, 50 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } void test_RotateRL() { AVLTreeint, int tree; tree.Insert({ 6, 60 }); tree.Insert({ 3, 30 }); tree.Insert({ 9, 90 }); tree.Insert({ 7, 70 }); tree.Insert({ 4, 40 }); tree.Insert({ 8, 80 }); tree.Print(); cout tree.IsBalanceTree() endl; cout endl; } int main() { test_RotateR(); test_RotateL(); test_RotateLR(); test_RotateRL(); return 0; }tree.IsBalanceTree() 输出为 1 就能证明我们成功实现了 AVL树 的平衡如果不为1也能说明我们自己所实现的旋转代码或者插入代码出现了问题便于我们发现。结束语到此C AVL树的实现就讲解完了。AVL 树以 “平衡因子” 控平衡、“旋转操作” 修失衡将增删查效率稳定在(O(log N))是自平衡树的经典范式。其核心魅力在于用简洁的平衡逻辑高度差≤1和精准的旋转策略解决了不同场景下的失衡情况化解普通二叉搜索树退化的问题虽高频写场景下旋转开销略逊于红黑树但对平衡原理的直观呈现使其成为理解复杂自平衡结构的基石。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/
