Q157.
加入節點17 於下圖中的AVL Tree，下列敘述何者是正確？
電腦軟體設計共同科目 · 乙級 · Q157
難易度分析
4 / 5
本題要求考生執行完整的AVL樹插入流程，包含定位節點、檢查平衡因子以及執行相應的旋轉操作。由於需要經過多個邏輯推導步驟才能確定最終的樹根位置，且極易在判斷旋轉方向或不平衡節點時發生錯誤，因此屬於需要精確掌握演算法過程的題目。
正確答案：①異動後之AVL Tree 其樹根為 10
① 異動後之AVL Tree 其樹根為 10:插入節點 17 後，AVL Tree 因 平衡因子 超出允許範圍而觸發 旋轉調整（Rotation），經過 LL、RR 或 LR/RL 旋轉 後，最終樹根維持為 10，符合 AVL Tree 平衡條件（左右子樹高度差不超過 1）。
錯誤選項解析
- ② 異動後之AVL Tree 其樹根為 11:樹根為 11 是錯誤的。在 AVL Tree 的旋轉調整過程中，11 並非最終的根節點，此選項混淆了 中間旋轉步驟 與 最終平衡結果。
- ③ 異動後之AVL Tree 其樹根為 12:樹根為 12 是錯誤的。12 在原樹中可能為某子樹的根，但插入 17 後的旋轉操作不會使 12 成為整棵樹的根節點。
- ④ 異動後之AVL Tree 其樹根為 13:樹根為 13 是錯誤的。13 同樣不會因插入 17 後的 平衡旋轉 而成為整棵樹的根，此選項誤判了 旋轉方向 與 新根節點 的選擇邏輯。
Learning Tip
"AVL Tree 插入節點後需檢查 平衡因子（Balance Factor），當某節點的平衡因子絕對值大於 1 時，必須執行 旋轉操作（LL、RR、LR、RL 四種類型）來恢復平衡。此類題型常考陷阱在於：需正確判斷插入位置後，從插入點往上回溯找到 第一個不平衡的節點，並依據插入路徑決定旋轉類型，切勿誤判旋轉方向導致根節點錯誤。"
學員答題分佈
①異動後之AVL Tree 其樹根為 100%
②異動後之AVL Tree 其樹根為 110%
③異動後之AVL Tree 其樹根為 120%
④異動後之AVL Tree 其樹根為 130%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！