C++实现二叉平衡树(AVL)旋转 _ LL/RR/LR/RL四种情况【源码】

二叉平衡树的旋转，说白了就是通过几套标准动作，让树在插入或删除后重新恢复平衡。LL/RR 是单次旋转，核心是把子节点提为新根，同时更新两个节点的高度；而 LR/RL 则是两次单旋的组合，需要先修正子树再旋转根，总共涉及三个节点的高度更新。插入操作一旦遇到失衡，立刻旋转并返回，后续不再向上回溯；但删除操作不同，一次旋转可能不够，必须持续检查直到根节点。

LL/RR旋转的实现关键在更新高度和子树重连

LL 和 RR 是单旋转，核心动作是把失衡节点的子节点“提上来”做新根，原根降为子节点。容易漏掉的是：旋转后必须重新计算两个参与节点的高度，否则后续平衡判断会出错。

常见错误现象：getHeight() 没在旋转后调用，导致 getBalanceFactor() 返回错误值，后续插入/删除反复触发无效旋转。

• LLRotate() 中，先保存 root->left 为 newRoot，再让 root->left = newRoot->right，最后 newRoot->right = root
• 旋转完成后必须按顺序调用 updateHeight(root) 和 updateHeight(newRoot)（先子后父，或先父后子都可，但不能漏）
• RR旋转逻辑对称，只是把 left 换成 right，其余结构完全一致

LR/RL旋转本质是两次单旋组合，不能直接交换指针

LR 不是“先L再R”的简单拼接——第一次旋转（L）后，原失衡节点的左子树已变，第二次旋转（R）的操作对象是它新的左孩子，不是原始节点。直接手写两层指针操作极易搞反顺序或漏更新高度。

使用场景：当 root 失衡且 root->left->right 高度更高时，必须用 LR；RL 同理，出现在 root->right->left 更高时。

• LR 旋转应拆解为：root->left = RRRotate(root->left)，再 LLRotate(root)（注意：第一次旋转返回新左子树，必须赋值回 root->left）
• RL 旋转同理：root->right = LLRotate(root->right)，再 RRRotate(root)
• 每次单旋后都要更新对应节点高度，LR/RL 共需更新 3 个节点高度（两次单旋各2个，但中间节点重叠，实际是3个）

insert() 中触发旋转的位置决定修复范围

A VL 插入后从插入点向上回溯，一遇到失衡节点就旋转，然后立即返回，不再继续向上检查。这是因为一次旋转最多影响当前子树根的高度，其父节点的平衡因子变化是确定的——旋转后整棵子树高度不变（LL/RR）或减1（LR/RL），所以父节点不会因此新增失衡。

错误做法：旋转后继续递归更新祖先高度，或在旋转后还对 root->parent 做平衡检查。

• 在 insert() 递归返回时，检查 getBalanceFactor(root)，若绝对值 > 1，则调用对应旋转函数，并直接 return newRoot
• 旋转函数返回新子树根，上层递归必须接收并赋值，例如：root = LRRotate(root)
• 旋转后无需再调用 updateHeight() 对 root，因为旋转函数内部已处理

delete() 的平衡修复比 insert() 更复杂，需重复检查

删除可能导致某路径高度下降，进而使多个祖先连续失衡。与插入不同，一次旋转不能保证整条路径恢复平衡，必须在旋转后继续向上回溯检查。

典型坑：复用插入的旋转逻辑，删除后只修一层，结果树仍不平衡。

• 删除后回溯时，每层都要计算平衡因子；一旦失衡，旋转得到新根，然后以该新根为起点，继续向上检查（不是返回，而是继续执行父节点的平衡逻辑）
• LR/RL 在 delete 中间出现频率更高，因为删除常导致“短边更短”，触发异侧深子树补偿
• 务必确认 updateHeight() 在每次旋转后、以及删除叶子/单子节点后都正确执行，否则高度链断裂

高度更新和旋转后指针归属是最容易被跳过的两步，尤其在 delete 场景下，少一次 updateHeight() 或漏接旋转返回值，整棵树的 getBalanceFactor() 就全乱了。