企业官网建设流程全解析

平衡二叉树（AVL 树）通过维护每个节点的平衡因子（即左右子树高度之差）来确保整棵树的高度始终接近 $ \log_2 n $，从而保障查找、插入和删除操作的时间复杂度稳定在 $ O(\log n) $。当插入或删除节点导致某个节点的平衡因子绝对值超过 1 时，就需要进行旋转调整以恢复平衡。

根据失衡情况的不同，主要分为四种调整类型（图中展示了其中三种典型场景）：

LL 型：单向右旋（Right Rotation）

• 失衡原因：在节点 A 的左子树的左子树中插入新节点，使得 A 的左子树过高。
• 平衡因子变化：A 的平衡因子由 +1 变为 +2。
• 调整方式：
  • 将 A 的左孩子 B 提升为新的根节点；
  • A 成为 B 的右孩子；
  • B 原来的右子树变为 A 的左子树（避免断开连接）。
• 效果：整体高度降低，B 和 A 的平衡因子均变为 0，子树恢复平衡。

defright_rotate(A):B=A.left A.left=B.right B.right=A# 更新高度A.height=max(height(A.left),height(A.right))+1B.height=max(height(B.left),height(B.right))+1returnB# 新的根

RR 型：单向左旋（Left Rotation）

• 失衡原因：在节点 A 的右子树的右子树中插入新节点，导致 A 的右子树过高。
• 平衡因子变化：A 的平衡因子由 -1 变为 -2。
• 调整方式：
  • 将 A 的右孩子 B 提升为新的根；
  • A 成为 B 的左孩子；
  • B 原来的左子树变为 A 的右子树。
• 效果：恢复平衡，B 和 A 的平衡因子均为 0。

defleft_rotate(A):B=A.right A.right=B.left B.left=A# 更新高度A.height=max(height(A.left),height(A.right))+1B.height=max(height(B.left),height(B.right))+1returnB# 新的根

LR 型：先左后右双向旋转（Left-Right Rotation）

• 失衡原因：在 A 的左子树的右子树插入节点，造成“折线型”失衡。
• 平衡因子变化：A 的平衡因子由 +1 变为 +2，但其左孩子 B 的平衡因子为 -1。
• 调整逻辑：
  1. 对 A 的左孩子 B 执行左旋（转化为 LL 型）；
  2. 再对 A 执行右旋。
• 效果：中间节点 C 成为新根，整棵子树恢复平衡。

defleft_right_rotate(A):A.left=left_rotate(A.left)returnright_rotate(A)

注：还有一种对称情况是RL 型（先右旋再左旋），用于处理右子树的左子树插入导致的失衡。

背景拓展总结

AVL 树作为最早的自平衡二叉搜索树之一，核心优势在于：

• 严格的平衡条件（平衡因子 ∈ {-1, 0, 1}）；
• 每次插入最多触发一次路径上的旋转即可恢复平衡；
• 查找效率极高，适合读多写少的场景；
• 相较于普通二叉排序树，避免了退化成链表的风险。

虽然由于频繁旋转带来一定开销，现代应用中红黑树更常见，但 AVL 树仍是理解自平衡机制的重要基础。

RL型失衡是AVL树中四种不平衡情况之一，属于“折线型”插入导致的失衡。

✅失衡产生原因：

RL型（Right-Left Case）发生在：

在节点 A 的右子树的左子树中插入一个新节点，导致 A 的平衡因子从 -1 变为 -2。

具体结构如下：

• 节点 A 的右孩子为 B；
• 节点 B 的左孩子为 C；
• 新节点插入到 C 的子树中（左侧或右侧）；

这种插入方式使得 A 的右子树高度显著增加，但路径为“先右再左”，形成折线形态，称为 RL 型。

此时：

• A 的平衡因子 = 左子树高 - 右子树高 = h - (h+2) =-2（失衡）
• B 的平衡因子通常为 +1（因为C是B的左孩子且较重）

✅调整方法：先右旋再左旋（双向旋转）

步骤分解：

1. 对 B 进行单向右旋（Right Rotation）

   • 将 B 的左孩子 C 提升；
   • B 的左子树变为 C 的右子树；
   • C 的右子树接回 B 作为其左子树；
   • 此步将 RL 型转换为 RR 型；

2. 对 A 进行单向左旋（Left Rotation）

   • 将 C（已提升）作为新的根节点；
   • A 成为 C 的左孩子；
   • 完成平衡恢复。

最终结果：以 C 为根的新子树左右高度一致，所有节点恢复平衡。

defright_left_rotate(A):# 第一步：对右孩子 B 进行右旋（处理 RL → RR）A.right=right_rotate(A.right)# 第二步：对当前节点 A 进行左旋returnleft_rotate(A)

✅调整效果：

• 子树整体高度降低；
• 根节点变为原中间节点 C；
• 所有涉及节点的平衡因子恢复至合理范围（-1, 0, 1）；
• 时间复杂度仍为 $ O(\log n) $，仅需常数时间完成两次旋转。

📌 示例图示（文字描述）：

A (-2) A (-2) \ \ B (+1) 插入后 → B / / C C' / \ / \ [新节点] ... → 先对 B 右旋 → 得到： A (-2) \ C / \ B ... / ... → 再对 A 左旋 → 得到： C (0) / \ A B / / ...