旋转

概述

旋转（rotation） 是红黑树（以及 AVL 树等自平衡二叉搜索树）中的基本局部结构调整操作。旋转通过改变节点之间的父子关系来改变树的结构，分为**左旋（LEFT-ROTATE）和右旋（RIGHT-ROTATE）**两种。旋转操作在 $O(1)$ 时间内完成，是保持红黑树平衡的核心手段。

定义

左旋 LEFT-ROTATE(T, x)

对节点 $x$ 执行左旋操作，假设 $x$ 的右子节点 $y$ 不为 NIL。左旋将 $x$ 与其右子节点 $y$ 的位置进行”局部交换”：$y$ 上升到 $x$ 的位置，$x$ 变为 $y$ 的左子节点，$y$ 的原左子节点变为 $x$ 的右子节点。

右旋 RIGHT-ROTATE(T, y)

右旋是左旋的对称操作。对节点 $y$ 执行右旋，假设 $y$ 的左子节点 $x$ 不为 NIL。右旋将 $y$ 与其左子节点 $x$ 的位置进行”局部交换”：$x$ 上升到 $y$ 的位置，$y$ 变为 $x$ 的右子节点，$x$ 的原右子节点变为 $y$ 的左子节点。

左旋操作详解

操作步骤

设 $x$ 为当前节点，$y=x.right$，$\alpha =x.left$，$\beta =y.left$，$\gamma =y.right$。

旋转前：          左旋后：
    x                y
   / \              / \
  α   y     →      x   γ
     / \          / \
    β   γ        α   β

LEFT-ROTATE(T, x) 的具体步骤：

1. 设 $y=x.right$（$y$ 不能为 NIL）
2. 将 $y$ 的左子树 $\beta$ “嫁接”为 $x$ 的右子树：$x.right=y.left$
3. 如果 $\beta$ 不为 NIL，设置 $\beta$ 的父指针：$y.left.p=x$
4. 将 $x$ 的父节点”嫁接”为 $y$ 的父节点：$y.p=x.p$
5. 如果 $x.p$ 为 NIL，则 $y$ 成为新的根节点：$T.root=y$
6. 否则如果 $x$ 是其父节点的左子节点：$x.p.left=y$
7. 否则：$x.p.right=y$
8. 将 $x$ 设为 $y$ 的左子节点：$y.left=x$，$x.p=y$

伪代码

LEFT-ROTATE(T, x)
  y = x.right
  x.right = y.left          // 将 y 的左子树转为 x 的右子树
  if y.left ≠ T.nil
      y.left.p = x
  y.p = x.p                 // 将 y "挂到" x 的父节点上
  if x.p == T.nil
      T.root = y
  elseif x == x.p.left
      x.p.left = y
  else
      x.p.right = y
  y.left = x                // 将 x 放到 y 的左边
  x.p = y

右旋操作详解

右旋是左旋的完全对称操作，只需将”左”与”右”互换。

旋转前：          右旋后：
      y            x
     / \          / \
    x   γ   →    α   y
   / \              / \
  α   β            β   γ

核心性质

时间复杂度

时间复杂度

旋转操作只修改常数个指针（最多修改 6 个指针），因此时间复杂度为 $O(1)$。

保持 BST 性质

BST 性质保持

旋转操作保持二叉搜索树的性质。旋转前后，树的中序遍历结果完全相同。

证明（以左旋为例）：

左旋前，中序遍历顺序为：$\alpha ,x,\beta ,y,\gamma$。

左旋后，$x$ 的左子树仍为 $\alpha$，右子树变为 $\beta$；$y$ 的左子树变为 $x$（包含 $\alpha$ 和 $\beta$），右子树仍为 $\gamma$。

中序遍历：先遍历 $y$ 的左子树（即以 $x$ 为根的子树），得到 $\alpha ,x,\beta$；然后访问 $y$；最后遍历 $y$ 的右子树 $\gamma$。

结果仍为：$\alpha ,x,\beta ,y,\gamma$。$■$

不保持红黑性质

重要

旋转操作不保持红黑性质。旋转可能破坏红黑树的某些性质（如性质 4 或性质 5），因此旋转通常作为修复操作的子步骤，与变色操作配合使用来恢复红黑性质。

左旋与右旋的对称性

• 左旋和右旋互为逆操作：对 $x$ 执行左旋得到 $y$ 后，再对 $y$ 执行右旋，可以恢复原来的树结构。
• 左旋要求 $x$ 有右子节点；右旋要求 $y$ 有左子节点。

章节扩展

旋转在红黑树中的两个核心应用场景：

场景	旋转次数	说明
插入修复 RB-INSERT-FIXUP	最多 2 次	Case 2 一次左旋 + Case 3 一次右旋（或对称）
删除修复 RB-DELETE-FIXUP	最多 3 次	Case 1 一次左旋 + Case 3 一次右旋 + Case 4 一次左旋（或对称）

参见

• 红黑树 — 红黑树的完整定义
• RB-INSERT-FIXUP — 插入修复中的旋转应用
• RB-DELETE-FIXUP — 删除修复中的旋转应用
• 二叉搜索树 — BST 的基本性质