树旋转简介

在离散数学中，树旋转（英语：Tree rotation）是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合。

树旋转包括两个不同的方式，分别是右旋转（以P为转轴）和左旋转（以Q为转轴）。两种旋转呈镜像，而且互为逆操作。

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

 ---  --- 
|Q||P|
 ---  --- 
/\rightrotation/\
 ---  --- -------------> ---  --- 
|P||Z||X||Q|
 ---  --- <------------- ---  --- 
/\leftrotation/\
 ---  ---  ---  --- 
|X||Y||Y||Z|
 ---  ---  ---  --- 

其中, 右旋转详细步骤如下图 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. 则右旋转过程可用伪代码表示为：

funcrotate_right(pivot):
letparent=pivot.parent
letroot=parent.parent
//R0
parent.left=pivot.right
ifpivot.right!=nil:pivot.right.parent=parent
//R1
pivot.parent=root
ifparent==root.left:
root.left=pivot
else:
root.right=pivot
pivot.right=parent
parent.parent=pivot

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