基本介紹
- 中文名：樹旋轉
- 類型：子樹調整
- 對象：二叉樹
- 旋轉方式：左旋轉和右旋轉
- 特點：兩種旋轉呈鏡像，且互為逆操作
- 套用：需要調整樹的局部平衡性的場合
實現,旋轉距離,
實現
假設從樹中任一節點 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:
root.left = 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。一種無需在根節點的某一子節點為轉軸時進行特殊處理的替代方案是讓樹的實際的根節點是一個特殊入口節點，而邏輯上的根節點作為該入口節點的某個子節點存在, 並避免任何以邏輯根節點為轉軸的旋轉。
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:
root.left = 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
