Q116.
假設n 代表資料數量，下列之描述何者是正確的？
電腦軟體設計共同科目 · 乙級 · Q116
難易度分析
3 / 5
本題要求對多種資料結構的特定操作時間複雜度有精確的掌握，且需區分 AVL Tree 在不同操作下旋轉次數的差異，以及區分樹的高度與走訪所有節點所需時間的區別，具有一定的陷阱性。
正確答案：②在AVL Tree 新增一個節點，所需之Rotation 時間複雜度為O(1)
② 在AVL Tree 新增一個節點，所需之Rotation 時間複雜度為O(1):在 AVL Tree 新增節點 時，最多只需執行一次旋轉（單旋轉或雙旋轉）即可恢復平衡，因此 Rotation 本身的時間複雜度為 O(1)。這是因為插入操作只會影響從插入點到根的路徑上第一個不平衡節點的子樹。
錯誤選項解析
- ① 在AVL Tree 刪除一個節點，所需之Rotation 時間複雜度為O(1):在 AVL Tree 刪除節點 時，可能從刪除位置沿路徑向上至根節點都需要檢查平衡並執行旋轉，最壞情況下需進行 O(log n) 次 Rotation，而非 O(1)。刪除操作可能引發多層次的平衡因子調整。
- ③ 刪除Minimum Heap 之最小值，所需之時間複雜度為O(1):刪除 Minimum Heap 的最小值（即根節點）後，需將最後一個元素移至根並執行 Heapify-Down（向下調整） 操作，沿樹高向下比較與交換，時間複雜度為 O(log n)，而非 O(1)。
- ④ 將二元樹以Preorder 順序排列，所需之時間複雜度為O(log n):Preorder 走訪（根-左-右）必須訪問二元樹中的每一個節點恰好一次，因此時間複雜度為 O(n)，而非 O(log n)。任何完整的樹走訪（Preorder、Inorder、Postorder）均需 O(n) 時間。
Learning Tip
"本題核心考點在於區分單一操作的時間複雜度與整體演算法複雜度的差異。AVL Tree 插入時最多只需一次旋轉（O(1)），但刪除時可能需要多次旋轉（O(log n)）。Heap 操作的插入與刪除均為 O(log n)，因為涉及向上或向下的調整路徑。樹的走訪必定是 O(n)，因為需訪問所有節點，切勿與樹的高度 O(log n) 混淆。"
學員答題分佈
①在AVL Tree 刪除一個節點，所需之Rotation 時間複雜度為O(1)0%
②在AVL Tree 新增一個節點，所需之Rotation 時間複雜度為O(1)0%
③刪除Minimum Heap 之最小值，所需之時間複雜度為O(1)0%
④將二元樹以Preorder 順序排列，所需之時間複雜度為O(log n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！