反饋

樹旋轉

鎖定

樹旋轉是在二叉樹中的一種子樹調整操作，每一次旋轉並不影響對該二叉樹進行中序遍歷的結果。樹旋轉通常應用於需要調整樹的局部平衡性的場合。樹旋轉包括兩個不同的方式，分別是。兩種旋轉呈鏡像，而且互為逆操作。

中文名: 樹旋轉
外文名: Tree rotation
類型: 子樹調整

對象: 二叉樹
旋轉方式: 左旋轉和右旋轉
特點: 兩種旋轉呈鏡像，且互為逆操作
應用: 需要調整樹的局部平衡性的場合

樹旋轉簡介

在離散數學中，樹旋轉（英語：Tree rotation）是在二叉樹中的一種子樹調整操作, 每一次旋轉並不影響對該二叉樹進行中序遍歷的結果. 樹旋轉通常應用於需要調整樹的局部平衡性的場合。^[1]

樹旋轉圖示

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

下圖示意了兩種樹旋轉過程中, 子樹的初態和終態：

        +---+                          +---+
        | Q |                          | P |
        +---+                          +---+
       /     \     right rotation     /     \
    +---+   +---+  ------------->  +---+   +---+
    | P |   | Z |                  | X |   | Q |
    +---+   +---+  <-------------  +---+   +---+
   /     \          left rotation         /     \
+---+   +---+                          +---+   +---+
| X |   | Y |                          | Y |   | Z |
+---+   +---+                          +---+   +---+

其中, 右旋轉詳細步驟如下圖 R0, R1, R2 三個步驟所示, 左旋轉則如 L0, L1, L2 三個步驟所示。^[1]

                                                                  __
                                                                 /  \
                                     +---+                      /  +---+
                                     | 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. 則右旋轉過程可用偽代碼表示為：^[1]

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

樹旋轉旋轉距離

兩棵二叉樹之間的旋轉距離指的是, 其中一棵樹通過儘可能少的樹旋轉變換到另一棵樹, 此過程中所使用的旋轉次數. 對於一個包含相同個數節點的二叉樹集合, 它們兩兩之間的距離可以構成一個度量空間. 是否存在一個算法, 能在多項式時間內計算兩個二叉樹之間的旋轉距離, 目前還是一個未決問題。^[1]

參考資料

1. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. Massachusetts: The MIT Press, 2002. pp273-77. ISBN 0-07-013151-1

詞條統計

瀏覽次數：次
編輯次數：9次歷史版本
最近更新：涵宇Q （2022-04-04）

1 簡介
2 圖示
3 實現
4 旋轉距離

樹旋轉

目錄

樹旋轉簡介

樹旋轉圖示

樹旋轉實現

樹旋轉旋轉距離