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。

较高的旋转度首先不一定会打破规则，其次会变得太复杂，尽管乍一看似乎不是这样。