AVL旋轉 - 要旋轉哪個節點

Question

我已經閱讀了許多AVL樹的源代碼，但沒有找到解決此問題的人：當AVL樹不平衡時，應首先旋轉哪個節點？

假設我有樹：

10 
/\ 
    5 25 
    /
     20 

，我嘗試添加15，則根及其子25將是不平衡的。

10 
/\ 
    5 25 
    /
     20 
    /
    15 

我可以做的25 RR循環（或單個旋轉），導致下面的樹：

 10 
    /\ 
    5 20 
     /\ 
     15 25 

或RL旋轉（雙旋轉）約根，創建下列樹：

20 
/\ 
    10 25 
/\  
5 15 

我很困惑哪些輪換在這裏和類似情況下最合適。

Answer 1

此處的RR旋轉是正確的。輪換應儘快（儘可能低），因爲規則被破壞。這裏是25。

較高的旋轉次數不一定會破壞規則，其次會變得太複雜，儘管在第一眼看來似乎不是這樣。