AVL樹的旋轉。不同的可能性

Question

我有一個關於在AVL樹中插入的問題。我注意到在某些情況下，例如，在插入元素之後，父項和它的子項都打破了AVL條件。例如這裏https://www.youtube.com/watch?v=EsgAUiXbOBo，至少。 12:50，當插入1後，4和3都打破了AVL條件。我的問題是我們應該在哪個節點上進行輪換。離根最近的一個（在這種情況下是根本身）還是離根最近的那個，因爲在這種情況下我們會得到兩棵不同的樹？或者它是正確的嗎？

Answer 1

旋轉從底部開始（插入的節點）。

讓我們考慮將所有節點平衡到P（包含）。所以P的子樹是完全平衡的。我們去P的父母（Q）。 Q的子樹被檢查並（最終）旋轉。結果樹（如果執行旋轉，根可能已經改變）完全平衡。再次提升。