Skip to content

二叉树右单旋

· 2 min

右单旋示例

下面这棵局部二叉树中，根节点 A 的左子树高度大约为 3，而右子树 α 高度为 1 或者很小。两边差 2，也就是“左边过重”了。

       A
      / \
     B   α
    / \
   C   D
  /
 E

🙋如何旋转？

由于 A 的左子树明显比右子树更高（差 2），可以在 A 上执行一次 右单旋。对 A 做 右单旋 后，B 会“上移”成为局部子树的根，A 变成 B 的右孩子，原先 B 的右子树 D 移到 A 的左子树位置。

最终结构如下：

     B
    / \
   C   A
  /   / \
 E   D   α

代码实现

function rightRotate(root, pivotValue) {
  let pivot = root // 假设当前的根节点就是旋转节点
  let parent = null // 存储父节点
  let isLeftChild = false // 记录旋转节点是不是父节点的左子节点


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


  if (!pivot) return root


  // 记录旋转节点的左子节点，因为这个节点回头会成为新的根节点
  const leftNode = pivot.left
  if (!leftNode) return root // 没有左子树，无法右旋


  pivot.left = leftNode.right
  leftNode.right = pivot


  // 修正和 parent 之间的位置关系
  if (!parent) {
    root = leftNode
  } else {
    if (isLeftChild) {
      parent.left = leftNode
    } else {
      parent.right = leftNode
    }
  }


  return root
}

-EOF-