民國108年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第43題
假設n 代表資料數量,下列之描述何者是正確的?
題目
假設n 代表資料數量,下列之描述何者是正確的?
- (1) 在AVL Tree 刪除一個節點,所需之Rotation 時間複雜度為O(1)
- (2) 在AVL Tree 新增一個節點,所需之Rotation 時間複雜度為O(1)
- (3) 刪除Mini mum Heap 之最小值,所需之時間複雜度為O(1)
- (4) 將二元樹以Preorder 順序排列,所需之時間複雜度為O(log n)
官方答案
(2) 在AVL Tree 新增一個節點,所需之Rotation 時間複雜度為O(1)
解析
AVL樹插入新節點後，只需沿回溯路徑做一次單旋轉或雙旋轉即可恢復平衡，旋轉次數為常數，時間複雜度O(1)。刪除節點則可能使路徑上多個祖先相繼失衡，最壞需O(log n)次旋轉。最小堆刪除最小值時，要把最後一個元素搬到根，再向下篩選，複雜度為O(log n)，並非O(1)。前序走訪必須拜訪每個節點一次，時間為O(n)，不是O(log n)。故選2。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。