AVL树失衡的四种情况通过失衡节点及其子节点的平衡因子识别：LL（+2,+1）、RR（−2,−1）、LR（+2,−1）、RL（−2,+1）；旋转后须更新涉及节点的高度和平衡因子，并在插入/删除递归回溯中持续检查与修复。
AVL树失衡的四种情况怎么识别
AVL树在插入或删除后，只要某个节点的左右子树高度差（平衡因子）绝对值超过1，就失衡了。关键不是看整棵树，而是从插入/删除点向上回溯，找到第一个平衡因子为±2的节点——它就是旋转中心。这个节点的平衡因子和其子节点的平衡因子共同决定属于哪一种失衡：LL、RR、LR、RL。
-
LL：当前节点平衡因子为+2，左孩子的平衡因子为+1（或0）→ 右旋 -
RR：当前节点平衡因子为−2，右孩子的平衡因子为−1（或0）→ 左旋 -
LR：当前节点平衡因子为+2，左孩子的平衡因子为−1 → 先对左孩子左旋，再对当前节点右旋 -
RL：当前节点平衡因子为−2，右孩子的平衡因子为+1 → 先对右孩子右旋，再对当前节点左旋
注意：0是合法平衡因子，但会影响旋转类型判断；比如LL中左孩子平衡因子为0时仍用右旋，不能误判为LR。
旋转操作必须同步更新哪些字段
单次旋转（左旋/右旋）不只是改指针，还必须重算涉及节点的height和balance。常见错误是只调换父子关系，忘了更新高度——这会导致后续判断持续出错。
- 右旋（
rotateRight）后：原根节点height= max(left->left->height, left->right->height) + 1；新根节点height= max(root->left->height, root->right->height) + 1 - 所有旋转后，必须显式重新计算
balance=height(left)−height(right)，不能靠旧值推导 - 若使用父指针，旋转后还要修正父节点的子指针；若不用父指针（推荐），则上层递归需接收并返回新根
示例片段（右旋后高度更新）：
node->height = std::max(height(node->left), height(node->right)) + 1;<br>newRoot->height = std::max(height(newRoot->left), height(newRoot->right)) + 1;
立即学习“C++免费学习笔记（深入）”；
插入后递归回溯时如何高效更新平衡因子
AVL插入本质是BST插入 + 自底向上修复。不能插完再遍历找失衡点——那样O(n)。正确做法是在递归返回时，每层都重新计算当前节点height和balance，一旦发现abs(balance) > 1，立即旋转，并把旋转后的子树根返回给上层。
- 插入函数必须返回
Node*，让上层能接收旋转后的新根 - 每次递归返回前，先更新
node->height，再算node->balance，再判断是否旋转 - 旋转后，该子树高度可能不变或减1，但上层仍需重新计算——所以旋转不能中断回溯，要继续向上更新
典型结构：root = insert(root, val);，而非insert(root, val);——返回值不可丢。
为什么删除比插入更难处理平衡
删除可能引发多级连锁失衡，且同一路径上可能需要多次旋转。插入最多导致一次失衡（因只新增一个叶子），而删除后某子树高度减1，可能让多个祖先节点的平衡因子从±1变成±2。
- 删除后回溯路径上，每个节点都要检查
balance，且每次旋转后仍需继续向上检查（不能像插入那样“修好就停”） - 删除中的
LR/RL情形更易漏判：比如删右子树导致左子树相对变高，但左子树本身又刚被调整过，其balance可能是−1，此时是RL而非LL - 实际编码中，建议统一用“先更新高度→再算平衡因子→再判断旋转→返回新根”四步，不要为删除单独写逻辑分支
最易忽略的是：删除后某节点高度没变（比如删的是高度较小的子树），但平衡因子变了——此时仍需检查是否失衡，不能跳过。
