Skip to content

二叉树双旋

· 6 min

为什么会有双旋？

假设我们有三个节点： A（根），B 是 A 的左孩子，C 是 B 的右孩子。这个结构如下所示：

  A
 /
B
 \
  C

（1）只对 A 做“右旋”：假设我们对 A 做右单旋，B 会被抬上来当根，但此时 C 仍然夹在中间的位置，结果往往无法一次性平衡整棵树，甚至造成结构混乱。如下图所示：

   A(原根)           B(新根)
  /           ->   / \
 B                ?   A
  \
   C

C 可能会变成 A 的左子树或挂在其他地方，没有彻底解决“平衡问题”。因此，单次右旋只适合“左-左”失衡的情况，而“左-右”这种“Z 形”无法一次搞定。

（2）只对 B 做“左旋”：如果只对 B 做一个左旋，可以把 C 抬上去，但 A 这边依旧会和新的结构不匹配，整体依然可能失衡。

双旋转是如何解决问题的？

对于 LR 型失衡（即“左-右”），双旋的过程是：

  1. 先对“左子树”做一次“左旋”：也就是说，先在 B 上做左旋，处理 B—C 这一段。
  2. 再对“根”节点做一次“右旋”：也就是说，然后再在 A 上做右旋，处理 A—B（或 C） 这一段。

回到我们的例子，先看局部结构：

    A
   /
  B
   \
    C

第一步：在 B 上做左旋，对 B 做左旋，把 C 抬上来：

(原局部)        (左旋后)
    B              C
     \     ->     /
      C          B

那么整棵树的局部就变成：

    A
   /
  C
 /
B

此时虽然 A 的左子树根从 B 变成了 C，但从高度来看，“失衡点”依然在 A 上，只是我们已经把“Z 形”转成了“左-左”形。

第二步：在 A 上做右旋。现在可以对 A 做一次右旋，把 C 提上来，A 下移到 C 的右侧：

    (原局部)            (右旋后)
        A                  C
       /         ->       / \
      C                  B   A
     /
    B

最终形成：

   C
  / \
 B   A

C 成了新的子树根，B 在左，A 在右，整棵子树高度变为 2，各节点的左右子树高度相差都不超过 1，达到平衡。

如果出现“右子树过高，但在右子树的左边”这种“镜像”情形，就要做 RL 双旋。逻辑完全对称：

  1. 先对“右子节点”做一次 右旋。
  2. 再对当前节点做一次 左旋。
  A
   \
    B
   /
  C

第一步：对“右子节点 B”做“右旋”，我们先看局部子树 B -> C，对 B 做一次右旋，核心是：

旋转前

  B
 /
C

旋转后（右旋）

C
 \
  B

回到整棵局部，将这个结果接回 A，就变成了：

A
 \
  C
   \
    B

现在，A 的右子树根由 B 变成了 C。虽然 A 依旧不平衡，但我们已经把“C 在 B 左侧”的问题纠正成“B 在 C 右侧”，为下一步的“左旋”做准备。

第二步：对“根节点 A”做“左旋”，在 A 上做左旋，核心是：

旋转前

A
 \
  C
   \
    B

旋转后

  C
 / \
A   B

新的根节点是 C，左子树是 A，右子树是 B，现在 C 节点左右子树高度都为 1（分别只有一个节点 A 和 B），所以高度差 = 0，子树恢复平衡

这样就完成了 RL 双旋的过程：

  1. 先对右子节点 B 做一次右旋
  2. 再对根节点 A 做一次左旋

总结一下：双旋基本上就是先做一次旋转，然后紧接着再做一次反方向的旋转。

代码实现

/**
 * root - 二叉树的根节点
 * pivotValue - 要旋转的节点所对应的值
 */
function LRDoubleRotate(root, pivotValue) {
  let pivot = root // 假设当前要旋转的节点就是根节点


  // 1. 首先需要先去找旋转节点
  while (pivot && pivot.value !== pivotValue) {
    if (pivotValue < pivot.value) {
      pivot = pivot.left
    } else {
      pivot = pivot.right
    }
  }


  // 如果 pivot 不存在或者 pivot.left 不存在，无法做 LR 旋转
  if (!pivot || !pivot.left) return root


  // 先拿到旋转节点的左子字节的值
  const leftPivotValue = pivot.left.value
  // 进行左旋操作
  root = leftRotate(root, leftPivotValue)


  // 接着在再 pivot 自身做一个右旋转
  root = rightRotate(root, pivotValue)


  return root
}

AVL树、红黑树、2-3-4树这些树称之为自平衡搜索树，这些树之所以能够保证自平衡，就是在构建的途中不断的旋转从而使其平衡。有兴趣的同学可以下来自己研究一下这些类型的树。

-EOF-