樹旋轉是在二叉樹中的一種子樹調整操作，每一次旋轉并不影響對該二叉樹進行中序遍歷的結果。
實現
假設從樹中任一節點 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
旋轉距離
兩棵二叉樹之間的旋轉距離指的是，其中一棵樹通過盡可能少的樹旋轉變換到另一棵樹，此過程中所使用的旋轉次數。對于一個包含相同個數節點的二叉樹集合，它們兩兩之間的距離可以構成一個度量空間。是否存在一個算法，能在多項式時間內計算兩個二叉樹之間的旋轉距離，目前還是一個未決問。
參考資料 >