Q218.
關於AVL 樹，下列那些正確？
電腦軟體設計共同科目 · 乙級 · Q218
難易度分析
4 / 5
本題採複選形式，且選項設計包含多個容易混淆的定義陷阱，要求對 AVL 樹的平衡因子定義與操作後果有精確的掌握，需完整判別所有選項之正確與否方能得分。
正確答案 (複選)：②, ④
- ② 同一個節點的左右兩個子樹的高度差至多為1:此為 AVL 樹（平衡二元搜尋樹） 的核心定義：任意節點的 平衡因子（Balance Factor） 等於左子樹高度減右子樹高度，其值必須為 -1、0 或 1，確保樹保持近似平衡。
- ④ 新插入一個節點，至多需要兩次旋轉:插入新節點後若造成失衡，依據失衡類型（LL、RR、LR、RL 四種情況），單旋轉（LL/RR）需 1 次旋轉，雙旋轉（LR/RL）需 2 次旋轉，故至多需要 兩次旋轉 即可恢復平衡。
錯誤選項解析
- ① 同一階層的任兩個子樹的高度差至多為1:此描述混淆了 AVL 樹的平衡條件 對象。AVL 樹規範的是「同一節點」的左右子樹高度差，而非「同一階層」的不同子樹之間的高度關係，同一階層的子樹高度差可能大於 1。
- ③ 任何兩個樹葉節點所在階層的差值至多為1:AVL 樹並非 完全二元樹（Complete Binary Tree），不要求所有樹葉位於相鄰階層。只要每個節點的平衡因子維持在 ±1 以內即可，因此樹葉節點的階層差值可能大於 1。
Learning Tip
"AVL 樹 的常考陷阱在於混淆「節點的左右子樹高度差」與「樹葉階層差」或「同層子樹高度差」。需牢記平衡因子是針對「單一節點」定義，而非整層或樹葉。另外，插入操作最多 2 次旋轉，但刪除操作可能需要 O(log n) 次旋轉，兩者務必區分清楚。"
學員答題分佈
①同一階層的任兩個子樹的高度差至多為10%
②同一個節點的左右兩個子樹的高度差至多為10%
③任何兩個樹葉節點所在階層的差值至多為10%
④新插入一個節點，至多需要兩次旋轉0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！