題組內容

三、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 CaseWorst Case
Search O(log n)O(log n)
InsertO(log n)
O(log n)
DeleteO(log n)
O(log n)