平衡不平衡/部分平衡BST的複雜性？

Question

在AVL樹中，每次我們在插入和刪除時重新平衡時，它會花費一定數量的單次和雙次旋轉，因爲我們只需檢查從插入點或刪除點到根的路徑。

如果我們有一個不平衡樹，我們將不得不檢查每個可能的節點是否平衡，因此將花費O(n)來重新平衡不平衡樹。它是否正確？

Answer 1

確實需要花時間O（n）重新設置一個不平衡的樹，但不是因爲你提到的原因。在AVL樹中，插入和刪除可能需要Θ（log n）旋轉，如果樹在插入元素之前最大程度地不平衡。這可能需要O（n log n）時間來重新平衡樹，因爲您可能會對每n個節點執行O（log n）工作。

但是，使用其他算法，您可以在O（n）時間重新平衡樹。一個簡單的選擇是對樹進行一次遍歷以獲得按排序順序排列的元素，然後通過遞歸地自下而上構建樹來從這些元素重建最優BST。或者，您可以使用Day-Stout-Warren algorithm，它平衡O（n）時間和O（1）空間中的任何樹。

希望這會有所幫助！