树旋转

树旋转是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合. 树旋转包括两个不同的方式, 分别是左旋转和右旋转. 两种旋转呈镜像, 而且互为逆操作.

图示

下图示意了两种树旋转过程中, 子树的初态和终态

        +---+                          +---+
        | Q |                          | P |
        +---+                          +---+
       /     \     right rotation     /     \
    +---+   +---+  ------------->  +---+   +---+
    | P |   | Z |                  | X |   | Q |
    +---+   +---+  <-------------  +---+   +---+
   /     \          left rotation         /     \
+---+   +---+                          +---+   +---+
| X |   | Y |                          | X |   | Y |
+---+   +---+                          +---+   +---+

其中, 右旋转详细步骤如下图 R0, R1, R2 三个步骤所示, 左旋转则如 L0, L1, L2 三个步骤所示.

                                                                  __
                                                                 /  \
                                     +---+                      /  +---+
                                     | Q |                     /   | Q |
                           +---+     +---+              +---+ /    +---+
        +---+              | P |    /     \      R1     | P |/    /     \              +---+
        | Q |     R0       +---+   /     +---+ ----->   +---+    /     +---+   R2      | P |
        +---+   ----->    /     \ /      | Z |         /        /      | Z | ----->    +---+
       /     \         +---+   +---+     +---+      +---+    +---+     +---+          /     \
    +---+   +---+      | X |   | Y |                | X |    | Y |                 +---+   +---+
    | P |   | Z |      +---+   +---+                +---+    +---+                 | X |   | Q |
    +---+   +---+              __                                                  +---+   +---+
   /     \                    /  \                                                        /     \
+---+   +---+     L2       +---+  \                       +---+                L0      +---+   +---+
| X |   | Y |   <-----     | P |   \                      | P |              <-----    | Y |   | Z |
+---+   +---+              +---+    \ +---+      L1       +---+     +---+              +---+   +---+
                          /     \    \| Q |    <-----    /     \    | Q |
                       +---+     \    +---+           +---+     \   +---+
                       | X |      \        \          | X |      \ /     \
                       +---+     +---+    +---+       +---+     +---+   +---+
                                 | Y |    | Z |                 | Y |   | Z |
                                 +---+    +---+                 +---+   +---+

实现

上面的图示仅描述了如何进行局部变换, 在实际应用中, 还需要将原有父节点的父节点纳入考虑范围. 以上述左旋转为例, 如果 Q 是其父节点 root 的左子节点, 则在旋转完后 root 的左子节点需要修改指向节点 P. 但这一点并没有体现在上面的图示中.

在接下来的实现中, 假设从树中任一节点 N 能够藉由 N.left 访问其左子节点, N.right 访问其右子节点, N.parent 访问其父节点. 此外, 称旋转后变为父亲的节点为转轴 pivot, 称 pivot 在旋转前的父节点为 parent, 而 parent 在旋转前的父节点为 root. 则右旋转过程可用伪代码表示为

func rotate_right(pivot):
  let parent = pivot.parent
  let root = parent.parent
  // R0
  parent.left = pivot.right
  if pivot.right != nil: pivot.right.parent = parent
  // R1
  pivot.parent = root
  if parent == root.left:
    root.left = pivot
  else:
    root.right = pivot
  pivot.right = parent
  parent.parent = pivot

而左旋转可表示为

func rotate_left(pivot):
  let parent = pivot.parent
  let root = parent.parent
  // L0
  parent.right = pivot.left
  if pivot.left != nil: pivot.left.parent = parent
  // L1
  pivot.parent = root
  if parent == root.left:
    root.left = pivot
  else:
    root.right = pivot
  pivot.left = parent
  parent.parent = pivot

上述过程并不适用于当 parent 节点本身就是树的根节点的情况. 这种情况下, 需要以其它方式重设树的根节点为 pivot. 一种无需在根节点的某一子节点为转轴时进行特殊处理的替代方案是让树的实际的根节点是一个特殊入口节点, 而逻辑上的根节点作为该入口节点的某个子节点存在, 并避免任何以逻辑根节点为转轴的旋转.

如果从节点出发, 只能访问其两个子节点, 而无法访问其父节点, 那么上述方法也不适用. 这种情况下, root 节点亦是旋转的必要参数之一. 旋转过程的伪代码表示如下

func rotate_right(root, parent):
  assert root.left == parent || root.right == parent
  let pivot = parent.left
  // R0
  parent.left = pivot.right
  // R1
  if parent == root.left:
    root.left = pivot
  else:
    root.right = pivot
  pivot.right = parent

func rotate_left(root, parent):
  assert root.left == parent || root.right == parent
  let pivot = parent.right
  // L0
  parent.right = pivot.left
  // L1
  if parent == root.left:
    root.left = pivot
  else:
    root.right = pivot
  pivot.left = parent

旋转距离

两棵二叉树之间的旋转距离指的是, 其中一棵树通过尽可能少的树旋转变换到另一棵树, 此过程中所使用的旋转次数. 对于一个包含相同个数节点的二叉树集合, 它们两两之间的距离可以构成一个度量空间. 是否存在一个算法, 能在多项式时间内计算两个二叉树之间的旋转距离, 目前还是一个未决问题.