Q154.
加入節點12 於下圖中的AVL Tree，下列敘述何者是正確？
電腦軟體設計共同科目 · 乙級 · Q154
難易度分析
3 / 5
本題要求考生在插入新節點後，必須能精確分析 AVL Tree 的平衡狀態並執行對應的旋轉操作，以判定最終的樹根節點。由於涉及從不平衡偵測到旋轉演算法的完整推演過程，且需區分單旋轉與雙旋轉的結果，因此具有中等以上的邏輯推理難度。
正確答案：②異動後之AVL Tree 其樹根為10
② 異動後之AVL Tree 其樹根為10:插入節點12後，原AVL Tree在節點10的右子樹產生不平衡（Balance Factor > 1），需執行RR旋轉或RL旋轉調整，使得節點10成為新的樹根以維持左右子樹高度差≤1的平衡條件。
錯誤選項解析
- ① 異動後之AVL Tree 其樹根為7:AVL Tree 插入節點12後，若樹根為7表示未正確執行旋轉平衡操作。原樹結構在插入後會導致不平衡，需透過LL、RR、LR或RL旋轉調整，樹根不會維持在7。
- ③ 異動後之AVL Tree 其樹根為11:若樹根為11表示錯誤地選擇了中間值作為根節點。AVL Tree的旋轉規則是依據不平衡節點與其子節點的相對位置決定，並非取中位數，11在此結構中不會成為旋轉後的樹根。
- ④ 異動後之AVL Tree 其樹根為13:節點13若成為樹根，代表錯誤執行了旋轉方向。AVL Tree 的旋轉必須依據插入位置與不平衡節點的關係判斷，13在原樹中應為右側葉節點，不會因插入12而提升為根。
Learning Tip
"AVL Tree 為自我平衡二元搜尋樹，核心考點在於插入節點後計算各節點的Balance Factor（左子樹高度減右子樹高度），當絕對值大於1時需執行旋轉。常考陷阱包括：混淆單旋轉（LL/RR）與雙旋轉（LR/RL）的適用情境，以及誤判旋轉後的新根節點。實務上應先找出不平衡的最低祖先節點，再依據插入路徑決定旋轉類型。"
學員答題分佈
①異動後之AVL Tree 其樹根為70%
②異動後之AVL Tree 其樹根為100%
③異動後之AVL Tree 其樹根為110%
④異動後之AVL Tree 其樹根為130%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！