树旋转

图示

对一棵树进行旋转时，这棵树的根节点是被旋转的两棵子树的父节点，称为旋转时的根（英语：root）；如果节点在旋转后会成为新的父节点，则该节点为旋转时的转轴（英语：pivot）。
上图中，树的右旋操作以Q 为根、P 为转轴，会将树顺时针旋转。相应的逆操作为左旋，会以Q 为转轴，将树逆时针旋转。
理解树旋转过程的关键，在于理解其中不变的约束。旋转操作不会导致叶节点顺序的改变（可以理解为旋转操作前后，树的中序遍历结果是一致的），旋转过程中也始终受二叉搜索树的主要性质约束：右子节点比父节点大、左子节点比父节点小。尤其需要注意的是，进行右旋转时，旋转前根的左节点的右节点（例如上图中以Q 为根的B 节点）会变成根的左节点，根本身则在旋转后会变成新的根的右节点，而在这一过程中，整棵树一直遵守着前面提到的几个约束。相反的左旋转操作亦然。
如果将根记为Root、转轴记为Pivot、子节点中与旋转方向相同的一侧记为RS（旋转侧，英语：Rotation Side）、旋转对侧记为OS（英语：Opposite Side），则上图中Q 节点的RS 为 C、OS 为 P，将其右旋转的伪代码为：
Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot
该操作为常数时间复杂度。

中序不变

二叉树旋转前后，中序遍历的结果不变。因此树的任何部分旋转，对整棵树的元素顺序没有影响。上图中两棵树的中序遍历结果为：
左侧的树: ((A, P, B), Q, C)        右侧的树: (A, P, (B, Q, C))
由两者其中之一计算另一个很简单：
如果要将节点Q 右旋：
设 P 为 Q 的左子树。
将 Q 的左子树设为P 的右子树。
[将 P 的右子树的父节点设为Q]
将 P 的右子树设为Q。
[将 Q 的父节点设为P]
如果要将节点P 左旋：
设 Q 为 P 的右子树。
将 P 的右子树设为Q 的左子树。
[将 Q 的左子树的父节点设为P]
将 Q 的左子树设为P。
[将 P 的父节点设为Q]
其余节点间的连接不变。
树的左右旋转操作还可以组合执行，称作双旋转（英语：double rotation）。先将X 的右子树右旋、再将X 本身左旋，就是 X 的双左旋转（英语：double left rotation）。同理，先将X 的左子树左旋、再将X 本身右旋，就是 X 的双右旋转（英语：double right rotation）。
很多树形数据结构中都用到了树的旋转操作，例如AVL树、红黑树、伸展树、树堆等。因为是局部变形，只涉及5个节点，不需要检查整棵树，所以操作只需要常数时间。

实现

上面的图示仅描述了如何进行局部变换, 在实际应用中, 还需要将原有父节点的父节点纳入考虑范围. 以上述右旋转为例, 如果 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

旋转距离

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

参考文献

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. Massachusetts: The MIT Press, 2002. pp273-77. ISBN 0-07-013151-1