民國104年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第74題
依序讀入1 , 2 , 3 , 4 , 5 , 6 ,並建造一棵A V L 樹,下列那些正確?
題目
依序讀入1 , 2 , 3 , 4 , 5 , 6 ,並建造一棵A V L 樹,下列那些正確?
- (1) 3 與6 在同一階層
- (2) 1 與3 在同一階層
- (3) 3 為2 的父節點
- (4) 5 為6 的父節點
官方答案
(1) 3 與6 在同一階層、(2) 1 與3 在同一階層、(4) 5 為6 的父節點
解析
依序插入並旋轉：插入1、2、3時，以1為根的右右失衡，左旋後以2為根，左子1、右子3。插入4接在3右邊；插入5造成3右右失衡，左旋後4為3、5的父節點。插入6後，以2為根右子樹過高而失衡，對2左旋，最後根為4，左子樹為2（子節點1、3），右子樹為5（右子6）。因此第0層是4，第1層是2、5，第2層是1、3、6；3與6同層、1與3同層、5為6的父節點，故1、2、4正確；3是2的子節點，故3不正確。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。