AVL树失衡的四种情况是LL、RR、LR、RL，通过插入/删除后检查平衡因子（BF）是否绝对值大于1识别：LL为左子树的左子树插入，RR为右子树的右子树插入，LR为左子树的右子树插入，RL为右子树的左子树插入。
AVL树失衡的四种情况怎么识别
AVL树不是靠“自动”平衡，而是靠插入/删除后显式检查并旋转——关键在识别BF（平衡因子）变化触发的四种失衡模式：LL、RR、LR、RL。这四种对应节点的height差为±2，且子树高度分布不同。
实际调试时，别等整棵树跑完才查——每次insert或remove后立即调用updateHeight和getBalanceFactor，一旦发现abs(bf) > 1，就按父节点和插入路径回溯两层，看新节点落在哪边：
-
LL：新节点插在左子树的左子树 → 右旋node -
RR：新节点插在右子树的右子树 → 左旋node -
LR：新节点插在左子树的右子树 → 先左旋node->left，再右旋node -
RL：新节点插在右子树的左子树 → 先右旋node->right，再左旋node
旋转操作必须更新哪些字段
只改指针不更新height，下一次getBalanceFactor就错——旋转后至少两个节点的height变了，必须重算。常见错误是只更新被旋节点，漏掉子节点或祖父节点。
以rightRotate为例（node为失衡根）：
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
<pre class="brush:php;toolbar:false;">x->right = y;
y->left = T2;
// 必须重算：y 和 x 的 height，顺序不能反
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;}
注意：getHeight应返回node ? node->height : 0，避免空指针；max用std::max或三目运算，别手写比较逻辑出错。
insert后balance的调用时机和范围
不是在insert函数末尾统一balance，而是在递归回退路径上逐层检查——因为只有从插入点向上到根的路径可能失衡，其余子树BF不变。
典型写法是让insert返回新子树根，并在每层递归返回前做balance：
- 插入后先更新当前节点
height - 计算
bf = getBalanceFactor(node) - 若
bf > 1且key left->key→LL→rightRotate(node) - 若
bf > 1且key > node->left->key→LR→ 先leftRotate(node->left)再rightRotate(node) - 同理处理
bf 的<code>RR/RL
这里key必须和插入路径一致——如果插入时走的是node->left分支，那判断LR就得用node->left的key比较，不是当前node的key。
为什么remove比insert更容易出bug
remove后失衡可能发生在祖先路径多个位置，且替换节点（如中序前驱）本身可能带子树，导致旋转后局部height误差扩散。最常踩的坑是：删完没重新计算被删节点父节点的height，或旋转后没检查新根是否仍失衡。
稳妥做法是：在remove递归返回时，对当前节点执行和insert完全相同的updateHeight + balance流程，哪怕它没被直接删除——因为它的子树高度可能已变。
另外，remove中的双子节点情况，用中序前驱还是后继不影响正确性，但影响平衡效率：选高度大的那一侧替换，能减少后续旋转次数。不过多数实现为简化逻辑，统一用前驱或后继即可。
真正难调的是多层连续失衡——比如一次remove触发RL，旋转后新根又BF = -2且满足RR，必须继续旋转。别指望一次balance搞定，得循环或递归处理直到abs(bf) ≤ 1。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
