樹(shù)旋轉(zhuǎn)簡(jiǎn)介

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

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

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

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

其中, 右旋轉(zhuǎn)詳細(xì)步驟如下圖 R0, R1, R2 三個(gè)步驟所示, 左旋轉(zhuǎn)則如 L0, L1, L2 三個(gè)步驟所示。

__
/\
 --- / --- 
|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|
 ---  ---  ---  --- 

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

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

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

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