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

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

異動後之AVL Tree 其樹根節點為12

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

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

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

難易度分析

4 / 5

本題要求考生在插入新節點後，必須精確執行 AVL Tree 的平衡旋轉操作，並對變動後的樹形結構進行多維度的分析（包含根節點、葉節點數、節點分支度及走訪順序），分析過程較為複雜且容錯率低。

正確答案：②異動後之AVL Tree 其葉節點共有5 個

② 異動後之AVL Tree 其葉節點共有5 個:異動後的 AVL Tree 葉節點（無子節點）分別為 1、8、12、15、18，共計 5個，此敘述正確。

錯誤選項解析

① 異動後之AVL Tree 其樹根節點為12:插入節點17後，原 AVL Tree 在節點10處產生 RR型不平衡，經左旋轉後樹根變為 13 而非12。
③ 異動後之AVL Tree 其分支度為1 之節點共4 個:分支度為1的節點僅有 5（僅有左子節點1）與 11（僅有右子節點12），共 2個而非4個。
④ 異動後之AVL Tree 其Preorder 為 10,7,5,1,8,13,11,12,15,17,18:異動後 Preorder（根-左-右）走訪應為 13, 10, 7, 5, 1, 8, 11, 12, 17, 15, 18，與選項所列順序不符。

Learning Tip

"AVL Tree 插入節點後需檢查平衡因子（Balance Factor），若絕對值大於1則需進行旋轉調整。常見考題陷阱包含：RR型需左旋、LL型需右旋、RL型需先右旋再左旋、LR型需先左旋再右旋。本題插入17後引發雙重旋轉（節點10處左旋、節點15處RL旋轉），需逐步追蹤樹結構變化才能正確判斷樹根、葉節點數、Preorder走訪順序。"

學員答題分佈

①異動後之AVL Tree 其樹根節點為120%

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

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

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

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