algorithm - ピボットを中心に回転できません

Question

AVLツリーに新しい値を挿入しようとしています。新しい挿入は不均衡を引き起こします (ウィキペディアの記事によると、これは左右のケースに属するはずです)。したがって、回転が必要です。ただし、両方の子が親よりも小さくなるため、現在の状況ではローテーションすることはできません。

           15
         /    \
        10    27
       /  \      
      8   12

ここで 11 を挿入すると、構造が不均衡になります。

           15
         /    \
        10    27
       /  \      
      8   12
         /
        11

ウィキペディアの図によると、左のサブツリーの方が長く、左のサブツリーには右のサブツリーの方が長いため、これは左右のケースに該当するはずです。ただし、要素に4は左右のサブツリーがあり、回転が可能でした。しかし、ここで12は、左のサブツリーしかないため、回転すると次のようになります。

           15
         /    \
        12    27
       /  \      
      10   8
         /
        11

その結果、両方の子供が1212 歳未満になります。ここで何が間違っていますか?

Answer 1

回転を間違えているようです。間違ったバランス係数を持つ唯一のノードはルートなので、それを中心に回転します。

その場合、(ルートの左の子) のバランス係数をチェックする10必要があります。これは -1 であるため、2 つの異なる回転 (左右のケース) が必要です。

まず、この画像の左上部分のように、左に 10 回転します。

したがって、次のようになります。

           15
          /  \
         12  27
        / 
       10    
      /  \
     8   11           

次に、画像で説明されているように、次のローテーションに進みます。