AY 22-23 Final Exam - Question B2（Tree, AVL & Traversal）

題目設定

給定二元樹，插入序列為 [X, I, S, K, M, A]。樹的結構如下：

        X
      /   \
     S     I
      \
       K
      / \
     M   A

💡 說明：根節點為 X；X 的左小孩是 S、右小孩是 I；S 的右小孩是 K（S 的左小孩為空）；K 的左小孩是 M、右小孩是 A。

Part (a) Tree Traversal（樹的走訪）

Pre-order traversal（前序走訪）

X, S, K, M, A, I

順序口訣：中、左、右（Root, Left, Right）。

Post-order traversal（後序走訪）

M, A, K, S, I, X

順序口訣：左、右、中（Left, Right, Root）。

Part (b) Array Implementation（陣列實作法）

使用陣列表示法，從 Index 0 開始；若無節點請填 null。
核心公式 若父節點在索引 p，則：
左小孩位置 = 2p + 1
右小孩位置 = 2p + 2

IndexContent計算過程備註
0XRoot 節點
1SX 的左小孩 (2*0 + 1)
2IX 的右小孩 (2*0 + 2)
3nullS 的左小孩為空
4KS 的右小孩 (2*1 + 2)
5nullI 的左小孩為空
6nullI 的右小孩為空
7null(Index 3) 的左小孩為空
8null(Index 3) 的右小孩為空
9MK 的左小孩 (2*4 + 1)
10AK 的右小孩 (2*4 + 2)

Part (c) AVL Tree Construction（建構平衡樹）

插入序列：[5, 8, 27, 16, 11, 13]。以下逐步說明每次插入、何時失衡以及採用的旋轉。

1. Insert 5
5

樹只有一個節點，平衡。

2. Insert 8
  5
    \
     8

仍然平衡（高度差 ≤ 1）。

3. Insert 27
  5
    \
     8
      \
      27

🚨 失衡發生：節點 5 出現 Right-Right (RR) 失衡（右子樹連續偏右）。
✅ 解決方法：在節點 5 上做 Left Rotation (左旋轉)，結果如下：

   8
  /   \
 5    27
4. Insert 16
   8
  /   \
 5    27
      /
    16

插入 16 為 27 的左子節點，整體高度差符合規範，仍然平衡。

5. Insert 11
   8
  /   \
 5    27
      /
    16
   /
 11

🚨 失衡發生：節點 27 出現 Left-Left (LL) 失衡（左子樹連續偏左）。
✅ 解決方法：對節點 27 做 Right Rotation (右旋轉)，結果局部調整為：

   8
  /   \
 5    16
     /  \
   11   27
6. Insert 13
     8
   /     \
  5      16
        /  \
      11   27
        \
        13

🚨 失衡發生：向上檢查時，根節點 8 的平衡因子變為 -2（右側過高）。因為新節點 13 插入在 8 的右子(16)的左側(11的右側)，這是典型的 Right-Left (RL) 失衡。
✅ 解決方法：標準 雙旋轉 (Double Rotation)。先對 16 做右旋，再對 8 做左旋。執行後最終樹為：

       11
      /    \
     8      16
    /      /  \
   5     13   27

Part (d) Why AVL Tree is Preferred?（為何偏好 AVL 樹？）

核心理由：

  1. 在最壞的情況下（例如依序插入 1, 2, 3, 4, 5），普通的二元搜尋樹（BST）會退化成線性的「鏈結串列 (Linked List)」，導致搜尋的時間複雜度飆升至 O(n)。
  2. AVL 樹 透過在插入或刪除時維持嚴格的高度平衡（確保任一節點的左右子樹高度差 ≤ 1），並以旋轉來修正失衡。
  3. 因此，AVL 樹在最壞情況下仍能保證樹的高度維持在 O(log n)，大幅提升且穩定了搜尋、插入與刪除的效率。
💡 教授的 AVL 考試速記：
  • LL 失衡 (偏左偏左) ➔ 做 Right Rotation (右旋)。
  • RR 失衡 (偏右偏右) ➔ 做 Left Rotation (左旋)。
  • LR 失衡 ➔ 先對左子樹做 Left Rotation，再對自己做 Right Rotation。
  • RL 失衡 ➔ 先對右子樹做 Right Rotation，再對自己做 Left Rotation。
  • Array Representation 時，永遠不要忘記空節點 (null) 也要算佔據一個 Index 位置，否則子節點的 2p+1 公式會大亂！