binary-tree - AVLツリーのバランス調整

Question

以下のAVLツリーを考えます。

        23
       /    \     
   19        35
  /  \      /  \     
 8   20   27    40
               /
             38
             /
            36

右の40で1回転するだけで大​​丈夫ですか？次のようにします。

        23
      /    \     
   19        35
  /  \      /  \     
 8   20   27    38
               /  \
             36    40

それでも、左側のサブツリーと比較して-+1の高さを持つAVLプロパティに準拠しています。

答えでは、それは二重回転を行うので、上の35のサブツリーは次のようになります。

        23
      /    \     
   19        38
  /  \      /  \     
 8   20   35    40
         /  \
        27  36    

両方がheightプロパティに違反していない場合、いつ2回転するのか、いつ1回転するのかわかりません。

Answer 1

二重回転は、使用中の特定のAVLアルゴリズムが原因である可能性があります。どちらの答えも、私には有効なAVLツリーのように見えます。

Answer 2

元の質問が不平衡AVLツリーのみで（ノードが追加または削除される前の平衡ツリーではなく）与えられた場合、単一のローテーションが有効な答えです。

If the question provides the AVL tree before and after a node was added or removed, then the algorithm for rebalancing could result in the double rotation occurring.

Answer 3

Both answers are right, though according to the literature that I use:

The are four types of rotations LL, RR,LR and RL. These rotations are characterized by the nearest ancestor A, of the inserted node N, whose balance factor becomes 2.

The following characterization of rotation types is obtained:

1. LL: N is inserted in the left subtree of the left subtree of A
2. LR: N is inserted in the right subtree of the left subtree of A
3. RR: N is inserted in the right subtree of the right subtree of A
4. RL: N is inserted in the left subtree of the right subtree of A

これらのルールに従って、バランス係数が2になる最も近い祖先が40例にあり、の左側のサブツリーの左側のサブツリーに挿入が行われた40ため、LL回転を実行する必要があります。これらのルールに従って、最初の回答が選択された操作になります。

それでも、両方の答えは正しく、使用しているアルゴリズムとそれが従うルールによって異なります。