在AVL樹插入/刪除中需要多少次餘額檢查

Question

我一直在閱讀有關AVL樹的文獻，發現它沒有詳細闡述AVL樹插入/刪除中需要多少次餘額檢查。

例如，在插入一個節點後，我們是否需要檢查從新節點一直到根的平衡？或者我們可以在輪換之後停止嗎？

如何通過複製左側子樹中最右側節點的策略進行刪除？從新刪除的（左子樹中最右邊的節點）節點檢查根？我們可以在輪換之後停止嗎？

Answer 1

插入後，您需要更新樹中每個「父」的平衡因子，直到根;所以它是O（log n）更新的最大值。但是你只需要進行一次重組就可以將樹恢復到不變量。

刪除後，像插入，你必須更新樹上的平衡因子;所以再次是O（日誌）更新。但是，與插入不同，您可能會使用多重重構旋轉來將樹恢復爲不變量。

http://en.wikipedia.org/wiki/AVL_tree

Answer 2

我一直在尋找深一點，我發現，當你可以停止檢查：

• 當插入一個節點的上級節點的平衡因子爲0。
• 輪換後。這是以前肯定的結果。

http://www.superstarcoders.com/blogs/posts/efficient-avl-tree-in-c-sharp.aspx

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx