申論題 - 阿摩線上測驗

申論題資訊

試卷：104年 - 104 鐵路特種考試_高員三級_電力工程、電子工程：計算機概論#22604
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：104年
排序：0

題組內容

三、AVL 樹是學者 G.M.Adelson-Velsky 和 E.M.Landis，於 1962 年的發表論文《An algorithm for the organization of information》而成名。

申論題內容

(二) AVL 樹的搜尋、插入和刪除其時間複雜度為何？（5 分）

詳解 (共 2 筆)

詳解提供者：kkcs60584

向AVL樹插入，可以透過如同它是未平衡的二元搜尋樹一樣，把給定的值插入樹中，接著自底往上向根節點折回，於在插入期間成為不平衡的所有節點上進行旋轉來完成。因為折回到根節點的路途上最多有1.44乘log n個節點，而每次AVL旋轉都耗費固定的時間，所以插入處理在整體上的耗費為O(log n) 時間。從AVL樹中刪除，可以透過把要刪除的節點向下旋轉成一個葉子節點，接著直接移除這個葉子節點來完成。因為在旋轉成葉子節點期間最多有log n個節點被旋轉，而每次AVL旋轉耗費固定的時間，所以刪除處理在整體上耗費O(log n) 時間。

詳解提供者：我還有明天

皆為O(logN)

整理：

AVL Tree Time Complexity

	Average Case	Worst Case
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)