C++ AVL 树：平衡因子更新逻辑与四种旋转的完整实现

文章目录C AVL 树平衡因子更新逻辑与四种旋转的完整实现一、AVL 树的核心概念1.1 平衡因子AVL 的灵魂1.2 节点结构为什么要三叉链二、插入分两步走2.1 整体流程2.2 平衡因子更新的三条规则2.3 插入代码三、旋转四种情况的完整实现3.1 旋转的两条原则3.2 右单旋RotateR左左失衡3.3 左单旋RotateL右右失衡3.4 左右双旋RotateLR左孩子的右边插入了3.5 右左双旋RotateRL右孩子的左边插入了四、查找和 BST 完全一样五、验证怎么确认你的 AVL 树是对的六、总结C AVL 树平衡因子更新逻辑与四种旋转的完整实现二叉搜索树BST有个致命的缺陷插入顺序一旦是有序的比如 1、2、3、4、5树就退化成一根链表查找复杂度从 O(logN) 崩到 O(N)。AVL 树就是为了解决这个问题诞生的——它是第一种自平衡二叉搜索树通过严格控制左右子树高度差不超过 1保证任何情况下查找都稳定在 O(logN)。这篇文章不废话直接把 AVL 树的平衡因子更新逻辑、四种旋转左单旋、右单旋、左右双旋、右左双旋的完整代码和最容易出错的双旋平衡因子细节讲透。红黑树、B 树的旋转思路和它一脉相承吃透 AVL 的旋转后面全通。一、AVL 树的核心概念1.1 平衡因子AVL 的灵魂AVL 树同时满足两个条件是一棵合法的二叉搜索树左小右大任意节点的左右子树高度差绝对值不超过 1。为了量化高度差给每个节点引入平衡因子balance factor简称 bf平衡因子 右子树高度 - 左子树高度AVL 树铁律所有节点的平衡因子只能是 -1、0、1。bf 1右子树偏高bf 0左右等高bf -1左子树偏高只要某个节点的 |bf| 达到 2即 2 或 -2树就失衡了必须通过旋转修复。注意不同教材对平衡因子的定义可能相反有的用左-右有的用右-左本文统一用「右 - 左」后面所有代码和讲解都基于这个约定别混。1.2 节点结构为什么要三叉链templateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;// 关键父指针int_bf;// 平衡因子AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};和普通 BST 节点比AVL 节点多了两个东西_parent 父指针插入后需要从新节点一路向上回溯更新祖先的平衡因子没有父指针就回不去了。这是三叉链存在的唯一理由。_bf 平衡因子记录当前节点左右子树高度差判断是否需要旋转。二、插入分两步走2.1 整体流程AVL 插入分四步按二叉搜索树规则插入新节点从新节点一路向上更新祖先的平衡因子更新过程中若没出现失衡插入结束若出现失衡|bf| 2对失衡子树旋转旋转会同时降低子树高度不会再影响更上层插入结束。2.2 平衡因子更新的三条规则这是 AVL 的核心逻辑理解了它旋转就顺理成章。插入一个节点后它只会影响祖先节点的高度所以从新节点开始向上更新平衡因子新节点在 parent 的右子树parent 的右子树高度 1所以parent-_bf新节点在 parent 的左子树parent 的左子树高度 1所以parent-_bf--。更新后根据 parent 的 bf 值有三种走向更新后 bf更新前变化含义处理0-1→0 或 1→0原来一边高一边低插到了低的一边子树高度不变停止更新1 或 -10→1 或 0→-1原来两边一样高插入后一边高一子树高度 1继续向上更新2 或 -21→2 或 -1→-2原来就一边高又插到了高的那边失衡了旋转处理然后停止用大白话解释这三条bf 变成 0说明这颗子树补平了整体高度没变不会影响再往上的祖先所以到此为止。bf 变成 ±1这颗子树自己还平衡但高度确实涨了 1会波及上面的父节点所以要继续往上更新。bf 变成 ±2这颗子树已经不平衡了必须旋转。旋转的本质是把这颗子树调平衡的同时把高度降回插入前所以旋转后也不会影响更上层到此为止。2.3 插入代码boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}// 1. 按 BST 规则找到插入位置Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;// key 已存在插入失败}}// 2. 链接新节点curnewNode(kv);if(parent-_kv.firstkv.first)parent-_rightcur;elseparent-_leftcur;cur-_parentparent;// 3. 向上更新平衡因子while(parent){// 先更新 parent 的平衡因子if(curparent-_left)parent-_bf--;// 新节点在左左树变高bf 减elseparent-_bf;// 新节点在右右树变高bf 加if(parent-_bf0){break;// 补平了高度不变停止}elseif(parent-_bf1||parent-_bf-1){curparent;// 继续往上更新parentparent-_parent;}elseif(parent-_bf2||parent-_bf-2){// 失衡了旋转处理break;}else{assert(false);// 理论上不可能走到这里}}returntrue;}注意最后那段旋转逻辑我这里break占位了真正的旋转要等到插入完成后根据失衡位置单独调用对应旋转函数。实际工程里会把旋转的调用合并进这个 while 循环这里拆开是为了把更新平衡因子和旋转两件事讲清楚。三、旋转四种情况的完整实现3.1 旋转的两条原则所有旋转都遵循两条原则保持搜索树规则左小右大不能破坏让旋转的树从失衡变平衡同时降低高度。旋转共四种右单旋、左单旋、左右双旋、右左双旋。下面用抽象子树 a/b/c 表示高度为 h 的 AVL 子树h 0这样一套图就能覆盖所有情况。3.2 右单旋RotateR左左失衡触发场景某个节点的左子树的左子树插入节点导致该节点 bf 变成 -2。也就是左边太高且插在了左孩子的左边。核心步骤因为5 b子树的值 10把 b 子树变成 10 的左子树10 变成 5 的右子树5 变成新的根。voidRotateR(Node*parent){Node*subLparent-_left;// 5Node*subLRsubL-_right;// b 子树// 把 b 子树挂到 parent 的左孩子parent-_leftsubLR;if(subLR)subLR-_parentparent;// 保存 parent 的父节点因为旋转后要重新链接上层Node*parentParentparent-_parent;// 让 subL 成为新根parent 成为 subL 的右孩子subL-_rightparent;parent-_parentsubL;// parent 可能是整棵树的根也可能是局部子树if(parentParentnullptr){_rootsubL;// 是根更新 _rootsubL-_parentnullptr;}else{// 是局部子树把 subL 链到 parentParent 的正确位置if(parentparentParent-_left)parentParent-_leftsubL;elseparentParent-_rightsubL;subL-_parentparentParent;}// 旋转后 parent 和 subL 的平衡因子都归 0parent-_bfsubL-_bf0;}最容易漏的点旋转不只是改两个节点的指向还要处理subLR可能为空的中间子树的挂载判断 parent 是根还是局部子树分别更新_root或父节点的孩子指针旋转完更新平衡因子。漏掉任何一个树就断了或 bf 就错了。这是手写 AVL 时 bug 的重灾区。3.3 左单旋RotateL右右失衡和右单旋完全镜像。触发场景右子树的右子树插入节点bf 变成 2。因为10 b子树的值 15把 b 变成 10 的右子树10 变成 15 的左子树15 成为新根。voidRotateL(Node*parent){Node*subRparent-_right;// 15Node*subRLsubR-_left;// b 子树parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left)parentParent-_leftsubR;elseparentParent-_rightsubR;subR-_parentparentParent;}parent-_bfsubR-_bf0;}左单旋和右单旋完全对称理解了右单旋左单旋就是把 left/right 全部对调。3.4 左右双旋RotateLR左孩子的右边插入了触发场景左边高但插入位置不在左孩子的左子树a而在左孩子的右子树b。这种情况下单纯右单旋解决不了问题——因为对 10 来说是左边高但对 5 来说却是右边高是拐弯的失衡需要两次旋转先以 5 为旋转点做左单旋再以 10 为旋转点做右单旋。这里是最容易出错的地方双旋后三个节点的平衡因子不是简单归零要根据插入的具体位置分三种情况。我们把 b 子树进一步展开——b 的根是 8它有两个高度为 h-1 的子树 e 和 f。新节点插在 e、插在 f、还是 b 本身就是新节点旋转后的 bf 完全不同场景条件8 的 bf旋转后 5旋转后 8旋转后 10场景1h1插在 e 子树-1001场景2h1插在 f 子树1-100场景3h0b 就是新节点0000为什么不同因为双旋的本质是第一次左旋把 8 提上来8 的左子树e挂到 5 的右孩子第二次右旋把 8 提到最顶8 的右子树f挂到 10 的左孩子。所以插入位置在 e 还是 f直接决定了 e 归 5 还是 f 归 10进而决定了 5 和 10 谁变高。这就是三种场景的根源。代码实现的关键先记录 subLR 的 bf再旋转旋转会改 bf最后根据记录的 bf 还原三个节点的平衡因子voidRotateLR(Node*parent){Node*subLparent-_left;// 5Node*subLRsubL-_right;// 8intbfsubLR-_bf;// 先记录 8 的平衡因子RotateL(parent-_left);// 先对 5 左单旋RotateR(parent);// 再对 10 右单旋// 根据记录的 bf 还原三个节点的平衡因子if(bf0)// 场景3b 就是新节点{subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1)// 场景1插在 e 子树{subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1)// 场景2插在 f 子树{subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}这是整个 AVL 实现里最坑的一处很多人旋转完直接给三个节点 bf 都归零结果在某些插入序列下 bf 算错导致后续插入时旋转判断失灵最终树结构错误却查不出来。必须先存 bf、旋转、再按 bf 分支还原这个顺序不能乱。3.5 右左双旋RotateRL右孩子的左边插入了和左右双旋完全镜像。触发场景右边高但插入位置在右孩子的左子树。先以右孩子为旋转点做右单旋再以 parent 做左单旋。同样把 b 子树展开b 的根是 12e/f 是两个高度 h-1 的子树也分三种场景场景条件12 的 bf旋转后 10旋转后 12旋转后 15场景1h1插在 e 子树-1001场景2h1插在 f 子树1-100场景3h0b 就是新节点0000voidRotateRL(Node*parent){Node*subRparent-_right;// 15Node*subRLsubR-_left;// 12intbfsubRL-_bf;// 先记录 12 的平衡因子RotateR(parent-_right);// 先对 15 右单旋RotateL(parent);// 再对 10 左单旋if(bf0){subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf1)// 插在 f 子树{subR-_bf0;subRL-_bf0;parent-_bf-1;}elseif(bf-1)// 插在 e 子树{subR-_bf1;subRL-_bf0;parent-_bf0;}else{assert(false);}}注意右左双旋的 bf 分支和左右双旋是镜像的1和-1的位置对调了别照抄左右双旋的条件。四、查找和 BST 完全一样Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey)curcur-_right;elseif(cur-_kv.firstkey)curcur-_left;elsereturncur;}returnnullptr;}AVL 树的查找就是标准的二叉搜索树查找因为树始终平衡复杂度稳定 O(logN)。五、验证怎么确认你的 AVL 树是对的手写 AVL 最容易出的问题就是看着能跑但 bf 其实算错了。光靠肉眼看不出来必须写个校验函数反向验证int_Height(Node*root){if(rootnullptr)return0;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);returnleftHeightrightHeight?leftHeight1:rightHeight1;}bool_IsBalanceTree(Node*root){if(nullptrroot)returntrue;// 重新计算左右子树高度差和节点存储的 bf 对比intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;if(abs(diff)2){coutroot-_kv.first高度差异常endl;returnfalse;}if(root-_bf!diff){coutroot-_kv.first平衡因子异常endl;returnfalse;}return_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}核心思路不信任节点里存的 bf而是现场重新算一遍真实的高度差和存的 bf 对比。如果两者不一致说明你更新平衡因子的逻辑有 bug。这是发现 bf 错误的唯一可靠手段。测试时插入一堆随机值再调用校验函数voidTestAVLTree(){constintN100000;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i)v.push_back(rand()i);AVLTreeint,intt;for(autoe:v)t.Insert(make_pair(e,e));cout是否平衡t.IsBalanceTree()endl;// 应为 1cout树高t.Height()endl;// 10万节点约 17 层验证 O(logN)}10 万个随机节点的 AVL 树高度约 17 层log2(100000) ≈ 17如果你测出来的高度是几十上百说明旋转没生效、树退化了立刻检查旋转代码。六、总结AVL 用平衡因子右-左严格控制高度差 ≤ 1换来 O(logN) 的稳定查找代价是插入删除时要频繁旋转。平衡因子更新三条规则bf 变 0 停止、变 ±1 继续向上、变 ±2 旋转后停止。四种旋转LL 右单旋、RR 左单旋、LR 左右双旋、RL 右左双旋单旋 bf 归零双旋必须按插入位置分三种场景还原 bf——这是 AVL 最核心也最易错的点。旋转时别忘了处理中间子树挂载、根/局部子树判断、bf 更新三件事。写完必须写校验函数插入随机值反向验证 bf 是否正确这是发现隐藏 bug 的唯一手段。AVL 的旋转思路是后续红黑树、B 树的基础把这四种旋转和 bf 更新逻辑吃透后面学红黑树只需要理解颜色约束替代了高度约束这个思想转变旋转本身你已经会了。