民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第74題
依序讀入1 , 2 , 3 , 4 , 5 , 6 ,並建造一棵A V L 樹,下列那些正確?
題目
依序讀入1 , 2 , 3 , 4 , 5 , 6 ,並建造一棵A V L 樹,下列那些正確?
- (1) 2 與5 在同一階層
- (2) 2 為 1 的父節點
- (3) 6 為5 的父節點
- (4) 4 為2 的父節點
官方答案
(1) 2 與5 在同一階層、(2) 2 為 1 的父節點、(4) 4 為2 的父節點
解析
依序插入1、2、3時，節點1發生右右不平衡，對1做一次左旋，根成為2，左子1、右子3。插入4接在3右側，各節點平衡因子仍在容許範圍。插入5後，節點2的右子樹高3、左子樹高1，屬右右型，對2左旋，根改為4，左子2（子節點1、3）、右子5。插入6接在5右側，此時根4左右子樹高度皆為2，無需旋轉。最終2與5同在第2階層，2為1的父節點，4為2的父節點；6是5的右子節點，並非5的父節點。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。