树旋转是在二叉树中的一种子树调整操作，每一次旋转并不影响对该二叉树进行中序遍历的结果。

实现

假设从树中任一节点 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:

rootleft = 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:

rootleft = 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

旋转距离

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

参考资料