企业官网建设流程全解析

在平衡二叉树（AVL 树）中，双旋转和删除操作是维持树结构平衡的关键机制。当插入或删除节点导致树失衡时，需根据具体失衡类型进行相应的旋转调整。

1. 双旋转平衡处理

先左后右双旋转（LR 型）

• 场景：节点 A 的平衡因子为 1（左子树高），在其左子树的右子树中插入新节点，使 A 的平衡因子变为 2，树失衡。
• 操作步骤：
  1. 对 A 的左子节点 B 的右子树进行左旋（即以 B 的右子树根节点 C 为轴向左旋转），将插入点“上提”，转化为 LL 型；
  2. 再对节点 A 进行右旋，恢复整体平衡。
• 本质：通过两次旋转将插入引发的“折线型”不平衡转变为直线型并修复。

先右后左双旋转（RL 型）

• 场景：节点 A 的平衡因子为 -1（右子树高），在其右子树的左子树中插入新节点，使 A 的平衡因子变为 -2。
• 操作步骤：
  1. 对 A 的右子节点 D 的左子树进行右旋（以 E 为轴向右旋转）；
  2. 再对 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 做左旋（双旋转）

总结口诀（便于记忆）：

⚠️ 注意：删除操作也可能引发上述失衡，判断方式相同，但可能需要沿路径持续调整多个祖先节点。

# 判断失衡类型的伪代码示意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"