AVLローテーション - どのノードをローテーションするか

Question

私はAVLツリーについて多くのソースを読んでいますが、この問題に対処している人はいませんでした：AVLツリーがアンバランスになったとき、ルートとその子25の両方がアンバランスになり、

10 
/\ 
    5 25 
    /
     20 

と私は15を追加しようとしています：

と仮定すると、私は木を持っています。

10 
/\ 
    5 25 
    /
     20 
    /
    15 

Iは、次のツリーをもたらす、25のRRの回転（または単一回転）を行うことができ：ルート約

 10 
    /\ 
    5 20 
     /\ 
     15 25 

又はRLの回転（二重回転）を、次のツリーを作成します：

20 
/\ 
    10 25 
/\  
5 15 

ここでは、どの回転が最も適しているのか、同様の場合は混乱しています。

Answer 1

RRの回転はここでは正しいです。ルールは壊れているので、回転はすぐに（低い）実行する必要があります。ここは25人です。

最初の回転では必ずしもルールが破られるとは限らず、2番目に複雑すぎることもあります。