民國111年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第64題
關於AVL 樹,下列那些正確?
題目
關於AVL 樹,下列那些正確?
- (1) 任何兩個樹葉節點所在階層的差值至多為1
- (2) 同一階層的任兩個子樹的高度差至多為1
- (3) 新插入一個節點,至多需要兩次旋轉
- (4) 同一個節點的左右兩個子樹的高度差至多為1
官方答案
(3) 新插入一個節點,至多需要兩次旋轉、(4) 同一個節點的左右兩個子樹的高度差至多為1
解析
AVL 樹的平衡條件是：任一節點其左子樹與右子樹的高度差（平衡因子）絕對值不超過 1，因此選項4正確。插入新節點後，只要沿回溯路徑找到第一個失衡節點，做一次單旋轉（LL、RR）或一次雙旋轉（LR、RL）即可恢復平衡，故至多兩次旋轉，選項3正確。選項1錯誤：AVL 只限制每個節點兩側子樹的高度差，樹葉節點仍可能分布在不同階層，深度差可以大於 1。選項2錯誤：平衡條件約束的是同一節點的兩個子樹，不是同階層任意兩個子樹。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。