加入節點12 於下圖中的AVL Tree，下列敘述何者是正確？

電腦軟體設計共同科目 · 乙級 · Q155

異動後之AVL Tree 其葉節點共5 個

異動後之AVL Tree 其分支度為1 之節點共3 個

異動後之AVL Tree 其分支度為2 之節點共4 個

異動後之AVL Tree 其Preorder 為 13, 7, 5,1,8,10,11,12,15,18

難易度分析

4 / 5

此題要求對AVL樹的插入與旋轉機制有精確掌握。由於操作過程中涉及多次旋轉調整，且選項涵蓋了樹的結構屬性分析與走訪順序驗證，需要較高精度的邏輯推演與模擬能力。

正確答案：②異動後之AVL Tree 其分支度為1 之節點共3 個

② 異動後之AVL Tree 其分支度為1 之節點共3 個:分支度為 1 的節點指僅有一個子節點的節點，調整後的樹中節點 5（僅左子節點 1）、節點 8（僅右子節點 10）、節點 15（僅右子節點 18）共 3 個，敘述正確。

錯誤選項解析

① 異動後之AVL Tree 其葉節點共5 個:插入節點 12 後需進行 AVL 旋轉調整，最終樹的葉節點（無子節點）為 1、10、12、18，共 4 個而非 5 個。
③ 異動後之AVL Tree 其分支度為2 之節點共4 個:分支度為 2 的節點指同時具有左右子節點的節點，調整後的樹中僅有節點 7、11、13 共 3 個而非 4 個。
④ 異動後之AVL Tree 其Preorder 為 13, 7, 5,1,8,10,11,12,15,18:Preorder（前序走訪）順序為「根→左→右」，正確結果應為 13, 7, 5, 1, 11, 8, 10, 12, 15, 18，選項中 11 與 8 的位置顛倒。

Learning Tip

"AVL Tree 插入操作的核心考點在於插入後需檢查平衡因子（Balance Factor），當 BF 絕對值大於 1 時需執行 LL、RR、LR 或 RL 旋轉。本題陷阱在於插入節點 12 後會觸發連續兩次旋轉（先於節點 10 旋轉，再於節點 8 旋轉），許多考生僅執行單次旋轉導致樹結構計算錯誤。建議手動模擬插入過程，由插入點向上逐層檢查 BF 值，並正確判斷旋轉類型。"

學員答題分佈

①異動後之AVL Tree 其葉節點共5 個0%

②異動後之AVL Tree 其分支度為1 之節點共3 個0%

③異動後之AVL Tree 其分支度為2 之節點共4 個0%

④異動後之AVL Tree 其Preorder 為 13, 7, 5,1,8,10,11,12,15,180%

此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！