Skip to content

二叉树左单旋

· 3 min

单旋（Single Rotation）是最基本的“旋转”操作，用来修正二叉树中某些局部不平衡的情况。

单旋分为：

  1. 左单旋：一般用于修复右子树过重的情况
  2. 右单旋：一般用于修复左子树过重的情况

左单旋示例

下面这棵局部二叉树中，根节点 A 的左子树高度为 1，而右子树的高度为 3。两边高度相差 2，典型的“右边过重”。

  A
 / \
α   B
   / \
  C   D
       \
        E

🙋如何旋转？

对 A 做 左单旋 ，B “上移”成为局部子树的根，A 则变成 B 的左孩子，原先 B 的左子树 C 变成 A 的右子树。

下面是旋转后结果：

    B
   / \
  A   D
 / \   \
α   C   E

代码实现

/**
 * root - 整颗树的根几点
 * pivotValue - 想要旋转的节点所对应的值
 */
function leftRotate(root, pivotValue) {
  let pivot = root // 用于存储要旋转的节点，一开始临时将根节点作为我们要旋转的节点
  let parent = null // 存储节点的父节点
  let isLeftChild = false // 记录当前要旋转的节点是否是父节点的左子节点


  // 1. 根据这个 pivotValue 找到要旋转的节点
  while (pivot && pivot.value !== pivotValue) {
    parent = pivot
    if (pivotValue < pivot.value) {
      pivot = pivot.left
      isLeftChild = true
    } else {
      pivot = pivot.right
      isLeftChild = false
    }
  }


  // 代码来到这里的时候，pivot 对应的就是要旋转的那个节点


  // 如果找不到 pivot 节点，啥也不做，直接返回原来的 root 节点
  if (!pivot) return root


  // 接下来就该做旋转的操作
  const rightNode = pivot.right // 记录旋转节点的右子节点，因为这个右子节点会成为新的根节点
  if (!rightNode) return root // 如果没有右子节点，无法左旋，直接返回原来的 root


  // 做左旋的时候，rightNode 的左子树会成为旋转节点的右子树
  pivot.right = rightNode.left


  // 原本的旋转节点，会成为新根节点的左子树
  rightNode.left = pivot


  // 接下来需要让 rightNode（新根节点）接替 pivot（旋转节点）在父节点的位置
  if (!parent) {
    root = rightNode
  } else {
    // 说明之前 pivot 是有父节点
    // 还需要判断之前的 pivot 旋转节点是父节点的左子节点还是右子节点
    if (isLeftChild) {
      parent.left = rightNode
    } else {
      parent.right = rightNode
    }
  }


  return root
}


leftRotate(bst, 10)

举个例子：

 10
   \
    20
      \
       30

旋转后：

   20
  /  \
 10   30

-EOF-