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个。

更高的旋转首先不一定违反规则，其次会变得太复杂，尽管乍一看似乎并非如此。