在平衡二叉树（AVL 树）中，双旋转和删除操作是维持树结构平衡的关键机制
在平衡二叉树（AVL 树）中，双旋转和删除操作是维持树结构平衡的关键机制。当插入或删除节点导致树失衡时，需根据具体失衡类型进行相应的旋转调整。
1. 双旋转平衡处理
先左后右双旋转（LR 型）
- 场景：节点 A 的平衡因子为 1（左子树高），在其左子树的右子树中插入新节点，使 A 的平衡因子变为 2，树失衡。
- 操作步骤：
- 对 A 的左子节点 B 的右子树进行左旋（即以 B 的右子树根节点 C 为轴向左旋转），将插入点“上提”，转化为 LL 型；
- 再对节点 A 进行右旋，恢复整体平衡。
- 本质：通过两次旋转将插入引发的“折线型”不平衡转变为直线型并修复。
先右后左双旋转（RL 型）
- 场景：节点 A 的平衡因子为 -1（右子树高），在其右子树的左子树中插入新节点，使 A 的平衡因子变为 -2。
- 操作步骤：
- 对 A 的右子节点 D 的左子树进行右旋（以 E 为轴向右旋转）；
- 再对 A 进行左旋，恢复平衡。
- 目的：消除“折线型”失衡，转化为 RR 型后再处理。
2. 平衡二叉树的删除操作
核心逻辑：
- 若被删节点有两个子树，则用其左子树中序遍历的最后一个节点（即左子树的最大值）或右子树中序遍历的第一个节点（即右子树的最小值）替代之，从而将问题转化为删除只有一个子树的节点。
- 删除后，从被删节点位置沿路径向上回溯至根节点，逐层更新各节点的平衡因子。
- 若某节点的平衡因子变为 ±2，则判断其失衡类型（LL、RR、LR、RL），执行对应单旋或双旋操作重新平衡。
- 旋转后可能缩短子树高度，需继续检查祖先节点是否仍平衡，直至整条路径处理完毕。
时间复杂度：每次插入/删除最多引发 O(log n) 次旋转（实际通常仅需常数次），整体仍保持 O(log n)。
补充说明
AVL 树通过严格的平衡条件确保查找效率最优，但频繁的旋转增加了插入删除开销，适用于查询远多于修改的场景。后续如红黑树等结构在平衡性与维护成本之间做了折中。
# 示例：模拟 LR 型双旋转（简化示意）defrotate_LR(A):B=A.left C=B.right# 左旋 B 的右子树B.right=C.left C.left=B A.left=C# 右旋 Areturnrotate_right(A)defrotate_right(A):B=A.left A.left=B.right B.right=AreturnB判断一个节点属于 LL、RR、LR 或 RL 失衡类型，关键在于分析失衡节点的平衡因子以及其子树中导致失衡的插入（或删除）位置。以下是具体判断方法：
1. 前提条件
- 某节点 A 的平衡因子变为+2 或 -2，说明以 A 为根的子树失衡。
- 需根据 A 的子树结构进一步判断是哪种类型。
2. 判断规则
（1）LL 型（Left-Left）
- 表现：A 的平衡因子为+2，且其左子节点 B 的平衡因子为+1
- 原因：新节点插入在 A 的左子树的左子树中
- 形态：
A (+2) / B (+1) / C- 处理方式：对 A 执行右旋（单旋）
（2）RR 型（Right-Right）
- 表现：A 的平衡因子为-2，且其右子节点 D 的平衡因子为-1
- 原因：新节点插入在 A 的右子树的右子树中
- 形态：
A (-2) \ D (-1) \ E- 处理方式：对 A 执行左旋（单旋）
（3）LR 型（Left-Right）
- 表现：A 的平衡因子为+2，但其左子节点 B 的平衡因子为-1
- 原因：新节点插入在 A 的左子树的右子树中
- 形态：
A (+2) / B (-1) \ C- 处理方式：先对 B 做左旋，再对 A 做右旋（双旋转）
（4）RL 型（Right-Left）
- 表现：A 的平衡因子为-2，但其右子节点 D 的平衡因子为+1
- 原因：新节点插入在 A 的右子树的左子树中
- 形态：
A (-2) \ D (+1) / C- 处理方式：先对 D 做右旋，再对 A 做左旋（双旋转）
总结口诀（便于记忆）：
| 类型 | 平衡因子（根） | 子节点平衡因子 | 插入路径 | 旋转方式 |
|---|---|---|---|---|
| LL | +2 | +1 | 左 → 左 | 右旋（单） |
| RR | -2 | -1 | 右 → 右 | 左旋（单） |
| LR | +2 | -1 | 左 → 右 | 先左后右（双） |
| RL | -2 | +1 | 右 → 左 | 先右后左（双） |
⚠️ 注意：删除操作也可能引发上述失衡，判断方式相同，但可能需要沿路径持续调整多个祖先节点。
# 判断失衡类型的伪代码示意defget_balance_type(node):bf=get_balance_factor(node)ifbf==2:left_bf=get_balance_factor(node.left)ifleft_bf==1:return"LL"elifleft_bf==-1:return"LR"elifbf==-2:right_bf=get_balance_factor(node.right)ifright_bf==-1:return"RR"elifright_bf==1:return"RL"return"Balanced"