AVL树删除后需自底向上修复失衡：从父节点回溯，对首个平衡因子为±2的节点按LL/LR/RR/RL类型执行单旋或双旋，并严格更新涉及节点高度。
一、理解 AVL 树删除后的失衡类型与旋转触发条件
在 AVL 树中删除一个节点后，从被删节点的父节点开始向上回溯至根节点，途中每个祖先节点的平衡因子可能变为 -2 或 2，表明该子树失衡。失衡共分四种情形：LL（左左）、LR（左右）、RR（右右）、RL（右左），分别对应需执行单右旋、先左后右双旋、单左旋、先右后左双旋。修复必须沿回溯路径对首个失衡节点立即处理，且修复后需更新其高度并继续向上检查父节点是否仍失衡。
1、计算节点高度：若节点为空，高度为 -1；否则为 max(左子树高度, 右子树高度) + 1。
2、计算平衡因子：节点的平衡因子 = 左子树高度 - 右子树高度。
3、识别失衡类型：对当前失衡节点 N，若左子节点 L 的平衡因子 ≥ 0，则为 LL 型；若 L 的平衡因子 0，则为 RL 型。
立即学习“C++免费学习笔记（深入）”；
二、实现单右旋（Right Rotation）用于 LL 失衡
单右旋将失衡节点 N 的左子节点 L 提升为新子树根，N 成为 L 的右子节点；L 原有的右子树（若存在）转为 N 的左子树。该操作保持中序遍历不变，并恢复 N 所在子树的 AVL 性质。
1、保存 L = N->left。
2、将 N->left 设置为 L->right。
3、将 L->right 设置为 N。
4、依次更新 N 和 L 的高度：先更新 N（因其子树已变），再更新 L。
5、返回 L 作为该子树新的根节点。
三、实现单左旋（Left Rotation）用于 RR 失衡
单左旋将失衡节点 N 的右子节点 R 提升为新子树根，N 成为 R 的左子节点；R 原有的左子树（若存在）转为 N 的右子树。该操作同样维持中序顺序，并修正高度关系。
1、保存 R = N->right。
2、将 N->right 设置为 R->left。
3、将 R->left 设置为 N。
4、依次更新 N 和 R 的高度：先更新 N，再更新 R。
5、返回 R 作为该子树新的根节点。
四、实现先左后右双旋（LR Rotation）用于 LR 失衡
LR 失衡需先对 N 的左子节点 L 执行左旋，使其右子节点成为新的左子根，再对 N 执行右旋。该组合确保旋转后子树高度差重归 [-1, 1] 区间，且结构满足 BST 性质。
1、对 N->left 执行左旋，得到新左子节点 L_new。
2、将 N->left 设置为 L_new。
3、对 N 执行右旋。
4、返回右旋后的子树根节点。
五、实现先右后左双旋（RL Rotation）用于 RL 失衡
RL 失衡需先对 N 的右子节点 R 执行右旋，使其左子节点成为新的右子根，再对 N 执行左旋。该过程同步维护 BST 顺序与 AVL 高度约束。
1、对 N->right 执行右旋，得到新右子节点 R_new。
2、将 N->right 设置为 R_new。
3、对 N 执行左旋。
4、返回左旋后的子树根节点。
六、编写删除后自底向上平衡修复主逻辑
删除操作本身按 BST 规则进行：若节点有两个子节点，用中序后继替换并递归删除后继；否则用唯一子节点或空节点替代。删除完成后，在递归返回路径上逐层调用平衡修复函数。每次修复后必须重新计算当前节点高度，再判断是否需旋转。
1、若当前节点为空，直接返回空指针。
2、根据待删值与当前节点值比较，递归进入左子树或右子树执行删除。
3、递归返回后，重新计算当前节点高度。
4、计算当前节点平衡因子，若绝对值大于 1，则根据子节点平衡因子判定失衡类型并执行对应旋转。
5、返回经旋转或未旋转后的当前子树根节点。
七、关键修复点：旋转后必须强制更新涉及节点的高度
所有旋转操作均会改变参与旋转节点的子树结构，因此每次旋转结束后，必须显式调用 updateHeight() 更新旋转中涉及的每一个节点的高度，否则后续平衡因子计算将失效。未更新高度将导致上层节点误判是否失衡，引发修复遗漏或错误旋转。
1、定义 updateHeight(Node* n) 函数：若 n 非空，则 n->height = 1 + max(getHeight(n->left), getHeight(n->right))。
2、在单右旋中，先 updateHeight(N)，再 updateHeight(L)。
3、在单左旋中，先 updateHeight(N)，再 updateHeight(R)。
4、在双旋中，每次单旋内部已包含对应 updateHeight 调用，外层无需重复，但最终返回前需确保新根高度正确。
