C++ AVL树：平衡因子、四种旋转与插入维护

大家好，上一篇我们实现了二叉搜索树，但它有个硬伤：按顺序插数据会退化成一根单支链，查找从 O(logN) 掉到 O(N)。AVL 树就是在二叉搜索树上加一层"自平衡"——每次插入后顺手把歪掉的子树转回来，保证任意节点左右两边差不多高，增删查都稳定在 O(logN)。

先约定两个大白话说法，后面全程用：高度就是从某个节点往下走到最深的叶子一共要经过几层；**平衡因子（bf）**就是"右边高度 − 左边高度"，所以它等于1 说明右边偏重、等于 -1 说明左边偏重、等于 0 说明两边一样平。

这篇把节点结构、平衡因子更新和四种旋转的代码完整搬出来，并重点讲清楚每种旋转到底在什么时机用、转完 bf 各是多少。

目录

• 一、AVL 树与平衡因子
• 二、节点结构
• 三、插入后怎么更新平衡因子
• 四、什么时候用哪种旋转（重点）
• 五、右单旋
• 六、左单旋
• 七、左右双旋与三种情况
• 八、右左双旋与三种情况
• 九、插入与平衡校验代码
• 十、总结

一、AVL 树与平衡因子

AVL 树是最先发明的自平衡二叉搜索树。它要么是空树，要么满足：左右子树都是 AVL 树，且左右子树高度差的绝对值不超过 1。它名字来自两位前苏联学者 Adelson-Velsky 和 Landis 1962 年的论文。

为了观察和控制平衡，每个节点带一个平衡因子（bf）。本文和代码统一采用：

bf = 右子树高度 − 左子树高度

所以任意节点的 bf 只能是 0、1、-1。注意这个口径和有些教材"左减右"相反，代码全程一致，不要记混。

为什么允许高度差为 1，而不是必须为 0？不是不想设计成完全等高，而是像 2 个节点、4 个节点这种结构天然做不到两边完全等高，最优也只能差 1。取"不超过 1"是做得到的最严格平衡。整体节点分布和完全二叉树接近，高度控制在 logN，增删查也就是 O(logN)，相比二叉搜索树有了本质提升。

补充一句：AVL 并不是非带平衡因子不可——也有不带 bf 的写法，靠临时遍历左右子树取高度差来判断。但每次现算代价高，所以实际实现都在节点里存一个 bf，像风向标一样直接告诉我们这棵子树偏左还是偏右。本文统一讲带_bf的版本。

二、节点结构

相比二叉搜索树，AVL 节点多了_bf和_parent：_parent用来沿父链向上更新平衡因子。下面是完整节点结构（和工程代码一致）。

template<classK,classV>structAVLTreeNode{pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;// balance factorAVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:// 旋转... 这里没写，成员函数在下面private:Node*_root=nullptr;};

三、插入后怎么更新平衡因子

插入规则和二叉搜索树一样：按 key 大小走到空位挂新节点。维护的核心就是从新节点出发，沿_parent往上更新 bf。

更新原则：新节点挂在 parent 的右边，parent 的_bf++；挂在左边，_bf--。只有子树高度真的变了，parent 的 bf 才会跟着变；而 parent 这棵子树的高度变没变，又决定了要不要继续往它父亲那里传。往上更新时只会出现下面三种情况（括号里是笔记里的典型变化过程）：

• bf 变成 0（比如从 -1 变 0，或从 1 变 0）：说明更新前 parent 本来就一边高一边矮，新节点恰好插在了矮的那一边，把矮的补齐了。结果这棵子树的总高度没变，父亲的 bf 不受影响，更新到此为止；
• bf 变成 1 或 -1（比如从 0 变 1，或从 0 变 -1）：说明更新前 parent 左右一样平，新节点插下去后一边高了。虽然子树仍然满足平衡要求，但它的高度比之前多了 1，这个变化会传递给它的父亲，所以要继续往上走；
• bf 变成 2 或 -2（比如从 1 变 2，或从 -1 变 -2）：说明更新前 parent 本来就一边高一边矮，新节点又偏偏插在高的那一边，让高的更高、彻底失衡。这时不能再往上更新了，必须旋转。旋转有两个目标：① 把这棵子树重新转平衡；② 把它的高度降回插入新节点之前的高度。正因为高度被压回去了，旋转完也就不用再往上更新，整支插入结束。

最后还有一种自然停止：一路更新到了根节点，根的父亲是空，循环自然结束——哪怕根的 bf 最后是 1 或 -1，也没有上层需要它影响了。

四、什么时候用哪种旋转（重点）

先记住旋转的两条原则，所有旋转都不违背：

1. 不能破坏搜索树规则——转完任意节点仍然满足"左 < 它 < 右"，只是上下左右的挂法变了；
2. 把歪掉的子树重新转平衡，并且顺便把它的高度压回插入前。只要高度压回去了，上层就不用再管。

拿到第一个失衡节点parent（bf 刚变成 ±2 的那个），先看它的 bf 是正还是负，再看高的那一侧孩子的 bf，就能确定用哪种旋转：

一句话记：外侧高（LL/RR）单旋一次；内侧高（LR/RL）单旋转不动，先把内侧折成外侧，再单旋。

五、右单旋

什么时候触发：parent（10）的 bf 从 -1 变成 -2，说明左边太高了。看上图，以 10 为根，它的左孩子是 5，5 的左边挂 a 子树、右边挂 b 子树，10 的右边挂 c 子树；a/b/c 是三棵抽象出来的、高度都为 h 的 AVL 子树（h≥0，代表所有右单旋的通用形态）。10 可能是整棵树的根，也可能只是上层某个节点的子树根。

插入后发生了什么：新节点插在 a 子树里，a 的高度从 h 变成 h+1。从新节点开始沿父链往上更新：先更新 5，再更新 10——5 的 bf 从 0 变成 -1，10 的 bf 从 -1 变成 -2。此时以 10 为根的这棵子树左右高度差是 2，左边太重，必须往右边"压"一下。

旋转具体怎么动（对照中间图到右图）：

1. 因为大小关系是5 < b 子树所有值 < 10，b 子树既不能留在 5 下面、也不能留在 10 的右边，正确位置是 10 的左边——所以先把 b 从 5 的右孩子摘下来，挂成 10 的左孩子；
2. 把 10 降下来，挂成 5 的右孩子；
3. 5 升上去，成为这棵子树新的根。

这样转完，大小关系完全没乱（a<5<b<10<c 依然成立），左右高度差也回到了 1 以内；更关键的是，这棵子树插入后高度一度涨到 h+3，右旋后又降回 h+2，和插入前完全一样。子树高度一旦回到插入前，就不会再影响上层，所以旋转完不必继续往上更新，这一支的插入到此结束。如果 10 原本只是上层的子树根，5 还要接回它爷爷原来接 10 的那个位置（原来 10 是爷爷的左孩子，5 就接左边；是右孩子就接右边）。

旋转部分之上还有没有节点：没旋转之前parent还有父亲节点的时候，即parent不是根节点的时候，我们把parent的父节点记为parentParent。旋转之后要更新parentParent的孩子指向。parentParent的左子树可能旋转部分，右子树也可能是，都要考虑
参考如下图

无论是右单旋、左单旋还是左右双旋、右左双旋都是要这么考虑，我只示意这一次，下面不画了

右单旋的完整实现如下：

//右单旋的实现voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;//这个时候要考虑subLR是不是空节点//按照逻辑来说，subLR的父节点要更新成parent。但是subLR如果是空节点就没这一说if(subLR)subLR->_parent=parent;//考虑parent还有父亲Node*parentParent=parent->_parent;subL->_right=parent;parent->_parent=subL;if(parentParent==nullptr){_root=subL;subL->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subL;}else{parentParent->_right=subL;}subL->_parent=parentParent;}parent->_bf=subL->_bf=0;}

六、左单旋

左单旋和右单旋是镜像对称，只是把左右反过来。

什么时候触发：parent（10）的 bf 从 +1 变成 +2，右边太重。以 10 为根，右孩子是 15，15 的左边挂 b 子树、右边挂 a 子树，10 的左边挂 c 子树，a/b/c 同样是高度为 h 的抽象子树。

插入后发生了什么：新节点插在 a 子树（15 的右边）里，a 从 h 变 h+1，沿父链更新 15 和 10 的 bf——15 从 0 变 +1，10 从 +1 变 +2。

旋转具体怎么动：

1. 大小关系是10 < b 子树所有值 < 15，b 子树应挂到 10 的右边——先把 b 从 15 的左孩子摘下，挂成 10 的右孩子；
2. 把 10 降下来，挂成 15 的左孩子；
3. 15 升上去成为新根。

转完同样恢复搜索树大小关系、把子树高度降回插入前，上层不再受影响。右单旋是"左边太高向右压"，左单旋就是"右边太高向左压"，三步一一对应。

//左旋voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*parentParent=parent->_parent;subR->_left=parent;parent->_parent=subR;if(parentParent==nullptr){_root=subR;subR->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}parent->_bf=subR->_bf=0;}

七、左右双旋与三种情况

什么时候用：parent bf=-2，但高在左孩子的右边——也就是 subL（5）的右孩子 subLR（8）那一侧高。这时直接右单旋压不住，得先对 5 左旋、再对 10 右旋，中间节点 8 成为新根。

为什么单旋转不动：右单旋解决的是"左孩子的左边高"（a 侧高）。现在高的却是左孩子的右边（8 这一侧）。如果硬对 10 右旋，把 5 提上去，8 那一坨还是悬在 5 右边、10 左边，高度差没真正降下来。所以思路是分两步：先在 5 这棵子树内部，对 5 来一次左单旋，把 8 从 5 的右边"翻"到 5 上面来；做完这步，高就从"5 的右边"变成了"5 的左边"，形状退化成右单旋能处理的 LL，再对 10 右单旋一次，8 就稳稳落到新根位置。

失衡结构（对照上图）：10 是 parent，左孩子 5 是 subL，5 的右孩子 8 是 subLR。平衡时 10 的 bf=-1、5 的 bf=0；5 左边挂 a（高 h），8 下面分 e、f 两棵高度 h-1 的子树，10 右边挂 c（高 h）。新节点插在 5 的右子树 b 里（也就是 8 这一侧），b 从 h-1 长高到 h，沿 8→5→10 更新：5 的 bf 从 0 变成+1（右边高了），10 的 bf 从 -1 变成-2，正式失衡。

旋转后到底是哪种 bf，取决于新节点插在 8 的左边（e）还是右边（f），或者 h=0 时 8 自己就是新节点。别死记结论：两步旋转做完后 8 成为新根、左边挂 5、右边挂 10，只要把每棵子树高度代进去，bf 自己就出来了。

• 场景 1（h≥1，新节点插在 e）：e 从 h-1 升到 h，此时 8 的 bf=-1（它左边高）。先以 5 为旋转点做一次左单旋，把 8 从 5 的右边翻上来；再以 10 为旋转点做一次右单旋，8 落到新根。转完 5 下面是 a（高 h）和 e（高 h），左右一样高，所以5 的 bf=0；10 下面是 f（高 h-1）和 c（高 h），右边比左边高 1，所以10 的 bf=+1；8 左右两棵子树等高，8 的 bf=0。

情景一视图中我将先左单旋再右单旋的过程画出来了。再其余场景和右左双旋的场景中，依次为参考，我就都不画了，只画这一次。

• 场景 2（h≥1，新节点插在 f）：f 从 h-1 升到 h，此时 8 的 bf=+1（它右边高）。两步旋转后，5 下面是 a（高 h）和 e（高 h-1），左边比右边高 1，所以5 的 bf=-1；10 下面是 f（高 h）和 c（高 h），左右一样高，所以10 的 bf=0；8 左右等高，8 的 bf=0。

• 场景 3（h=0）：插入前 a/b/c 都是空树，8（也就是 b）自己就是那个新节点，旋转前 8 没有左右孩子、bf=0。两步旋转后 5 和 10 下面都挂不出非空子树，三个节点 bf 全为 0。

可以看到：双旋不是把 bf 一刀切全置 0，而是要按旋转前 8 的 bf 分三种情况分别修正——这正是 RotateLR 里那个if (bf == 0) / else if (bf == -1) / else if (bf == 1)在做的事。

voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf==0){subL->_bf=0;subLR->_bf=0;parent->_bf=0;}elseif(bf==-1){subL->_bf=0;subLR->_bf=0;parent->_bf=1;}elseif(bf==1){subL->_bf=-1;subLR->_bf=0;parent->_bf=0;}//防御性编程else{assert(false);}}

八、右左双旋与三种情况

什么时候用：parent bf=+2，但高在右孩子的左边——subR（15）的左孩子 subRL（12）那一侧高。这是左右双旋的镜像：先对 15 右旋、再对 10 左旋，中间节点 12 成为新根。

为什么单旋转不动：左单旋解决的是"右孩子的右边高"（a 侧高），现在高的却是右孩子的左边（12 这一侧）。硬对 10 左旋，12 那一坨还是悬在 15 左边、10 右边，高度差没降下来。所以分两步：先对 15 右单旋，把 12 从 15 的左边"翻"到 15 上面；做完高就从"15 的左边"变成"15 的右边"，形状退化成左单旋能处理的 RR，再对 10 左单旋，12 落到新根。

失衡结构（对照上图）：10 是 parent，右孩子 15 是 subR，15 的左孩子 12 是 subRL。平衡时 10 的 bf=+1、15 的 bf=0；10 左边挂 c（高 h），12 下面分 e、f 两棵高度 h-1 的子树，15 右边挂 a（高 h）。新节点插在 15 的左子树 b 里（也就是 12 这一侧），b 从 h-1 长高到 h，沿 12→15→10 更新：15 的 bf 从 0 变成-1（左边高了），10 的 bf 从 +1 变成+2，正式失衡。

旋转后 12 成为新根、左边挂 10、右边挂 15。同样把各子树高度代进去：

• 场景 1（h≥1，插在 e）：e 从 h-1 升到 h，此时 12 的 bf=-1（它左边高）。先以 15 为旋转点做一次右单旋，再以 10 为旋转点做一次左单旋。转完 10 下面是 c（高 h）和 e（高 h），左右等高，10 的 bf=0；15 下面是 f（高 h-1）和 a（高 h），右边比左边高 1，15 的 bf=+1；12 左右等高，12 的 bf=0。

• 场景 2（h≥1，插在 f）：f 从 h-1 升到 h，此时 12 的 bf=+1（它右边高）。两步旋转后，10 下面是 c（高 h）和 e（高 h-1），左边比右边高 1，10 的 bf=-1；15 下面是 f（高 h）和 a（高 h），左右等高，15 的 bf=0；12 左右仍然等高，12 的 bf=0。

• 场景 3（h=0）：12 自己就是新节点，旋转前 bf=0，两步旋转后10、12、15 三个节点 bf 全为 0。

这三个分支对应 RotateRL 里bf == 0 / 1 / -1的三种修正，和左右双旋完全镜像。

voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf==0){subR->_bf=0;subRL->_bf=0;parent->_bf=0;}elseif(bf==1){subR->_bf=0;subRL->_bf=0;parent->_bf=-1;}elseif(bf==-1){subR->_bf=1;subRL->_bf=0;parent->_bf=0;}//防御性编程else{assert(false);}}

九、插入与平衡校验代码

下面是插入骨架和平衡校验的完整实现。插入里检测到 bf=±2 时留下了旋转的位置，把第四节的判断接进来即可。

boolinsert(){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first<kv.first){parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;// 更新平衡因子while(parent)//最坏的情况是更新到根，根的父亲是空，所以以此为判断条件{if(parent->left==cur){parent->_bf--;}else{parent->_bf++;}if(parent->_bf==0){break;}elseif(parent->_bf==1||parent->_bf==-1){parent=parent->_parent;cur=parent;}elseif(parent->_bf==-2||parent->_bf==2){//旋转//这里我太累了，实在不想写了，旋转相关接口都已经实现//大家根据情况，来分类施行不同旋转策略//.......break;}}returntrue;}int_Height(Node*root){if(root==nullptr)return0;intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);returnleftHeight>rightHeight?leftHeight+1:rightHeight+1;}bool_IsBalanceTree(Node*root){// 空树也是AVL树if(nullptr==root)returntrue;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);intdiff=rightHeight-leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if(abs(diff)>=2){cout<<root->_kv.first<<"高度差异常"<<endl;returnfalse;}if(root->_bf!=diff){cout<<root->_kv.first<<"平衡因子异常"<<endl;returnfalse;}// pRoot的左和右如果都是AVL树，则该树一定是AVLreturn_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

十

1. AVL = 高度平衡的二叉搜索树：bf = 右高 − 左高，取值只能是 0/±1；
2. 插入后沿父链更新 bf：变 0 停、变 ±1 继续上、变 ±2 旋转；
3. 旋转时机：parent bf=-2 看左孩子（-1 右单旋、+1 左右双旋），bf=+2 看右孩子（+1 左单旋、-1 右左双旋）；外侧高单旋、内侧高双旋；
4. 双旋后 bf 分三种：按新节点落在 subLR/subRL 的左、右还是 h=0，分别修正三个节点的 bf，不能一刀切全置 0；
5. 写完用_IsBalanceTree递归校验每个节点 bf 与真实高度差是否一致，是最稳的自测方式。
6. 本文只讲了插入场景；删除操作同样会引发 bf 变化和旋转（方向相反、更复杂），篇幅较长，我不太想讲了，以后有时间出吧，无限期延长讲删除的计划。