樹旋轉(zhuǎn)實現(xiàn)

上面的圖示僅描述了如何進行局部變換, 在實際應用中, 還需要將原有父節(jié)點的父節(jié)點納入考慮范圍. 以上述右旋轉(zhuǎn)為例, 如果 Q 是其父節(jié)點 root 的左子節(jié)點, 則在旋轉(zhuǎn)完后 root 的左子節(jié)點需要修改指向節(jié)點 P. 但這一點并沒有體現(xiàn)在上面的圖示中.

在接下來的實現(xiàn)中, 假設從樹中任一節(jié)點 N 能夠借由 N.left 訪問其左子節(jié)點, N.right 訪問其右子節(jié)點, N.parent 訪問其父節(jié)點. 此外, 稱旋轉(zhuǎn)后變?yōu)楦赣H的節(jié)點為轉(zhuǎn)軸pivot, 稱 pivot 在旋轉(zhuǎn)前的父節(jié)點為 parent, 而 parent 在旋轉(zhuǎn)前的父節(jié)點為 root. 則右旋轉(zhuǎn)過程可用偽代碼表示為：

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

樹旋轉(zhuǎn)包括兩個不同的方式，分別是右旋轉(zhuǎn)（以P為轉(zhuǎn)軸）和左旋轉(zhuǎn)（以Q為轉(zhuǎn)軸）。兩種旋轉(zhuǎn)呈鏡像，而且互為逆操作。

下圖示意了兩種樹旋轉(zhuǎn)過程中, 子樹的初態(tài)和終態(tài)：

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

其中, 右旋轉(zhuǎn)詳細步驟如下圖 R0, R1, R2 三個步驟所示, 左旋轉(zhuǎn)則如 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|
 ---  ---  ---  --- 

在離散數(shù)學中，樹旋轉(zhuǎn)（英語：Tree rotation）是在二叉樹中的一種子樹調(diào)整操作, 每一次旋轉(zhuǎn)并不影響對該二叉樹進行中序遍歷的結(jié)果. 樹旋轉(zhuǎn)通常應用于需要調(diào)整樹的局部平衡性的場合。

兩棵二叉樹之間的旋轉(zhuǎn)距離指的是, 其中一棵樹通過盡可能少的樹旋轉(zhuǎn)變換到另一棵樹, 此過程中所使用的旋轉(zhuǎn)次數(shù). 對于一個包含相同個數(shù)節(jié)點的二叉樹集合, 它們兩兩之間的距離可以構(gòu)成一個度量空間. 是否存在一個算法, 能在多項式時間內(nèi)計算兩個二叉樹之間的旋轉(zhuǎn)距離, 目前還是一個未決問題。