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。

较高的旋转次数不一定会破坏规则，其次会变得太复杂，尽管在第一眼看来似乎不是这样。