6

AVL ツリーから削除すると、最終的にいくつかのノードのバランスが崩れる可能性があることはよく知られています。私の質問は、2 回転が必要な最小サイズの AVL ツリーは何ですか (左右または左右の回転は 1 回転であると想定しています)。現在、削除すると 2 つのローテーションが発生する 12 個のノードを持つ AVL ツリーがあります。私のAVLツリーは次の順序で挿入しています:

8、5、9、3、6、11、2、4、7、10、12、1。

10、9を削除するとバランスが崩れて回転が発生します。そうすることで、8がアンバランスになり、別の回転が発生します。削除後に 2 回のローテーションが必要な小さなツリーはありますか?

jpalecek のコメントを読んだ後、私の本当の質問は次のとおりです。定数 k が与えられた場合、1 回の削除後に k 回のローテーションを持つ最小サイズの AVL ツリーは何ですか?

4

2 に答える 2

5

最悪の場合、4つのノードのツリーには1回のローテーションが必要です。最悪の場合の削除数は、リスト内の各用語とともに増加します：4、12、33、88、232、609、1596、4180、10945、28656、..。

これはSloaneのA027941N(i)=1+N(i-1)+N(i-2)であり、 forで生成できるフィボナッチタイプのシーケンスですi>=2, N(1)=2, N(0)=1。

これがなぜそうなのかを理解するために、最初に、不均衡なAVLツリーを回転させると、短い方の脚が長くなり、長い方の脚が犠牲になるため、高さが1つ低くなることに注意してください。

ノードがAVLツリーから削除されると、AVLアルゴリズムは、削除されたノードのすべての祖先をチェックして、潜在的なリバランスを確認します。したがって、あなたの質問に答えるには、特定の高さに対してノードの数が最小のツリーを特定する必要があります。

このようなツリーでは、すべてのノードがリーフであるか、バランス係数が+1または-1です。ノードのバランス係数がゼロの場合、これは、リバランスをトリガーせずにノードを削除できることを意味します。そして、リバランスによってツリーが短くなることはわかっています。

以下に、最悪の場合のツリーのセットを示します。シーケンスの最初の2つのツリーに続いて、各ツリーが前の2つのツリーを結合することによって構築されていることがわかります。また、各ツリーのすべてのノードがリーフであるか、ゼロ以外のバランス係数を持っていることもわかります。したがって、各ツリーには、ノード数の最大の高さがあります。

各ツリーについて、左側のサブツリーを削除すると、最悪の場合、回転が発生し、最終的にそのサブツリーの高さが1つ減少します。これにより、ツリー全体のバランスがとれます。一方、右側のサブツリーからノードを削除すると、最終的にツリーのバランスが崩れ、ルートが回転する可能性があります。したがって、適切なサブツリーが最も重要です。

最悪の場合、ツリー（c）とツリー（d）が削除時に1回転することを確認できます。

ツリー（c）はツリー（e）の右側のサブツリーとして表示され、ツリー（d）はツリー（f）の右側のサブツリーとして表示されます。ツリー（c）または（d）で回転がトリガーされると、ツリーが短くなり、ツリー（d）および（f）でルートが回転します。明らかに、シーケンスは継続します。

ツリー内のノードの数を数えると、これは私の元のステートメントと一致し、証明を完了します。

（下のツリーでは、強調表示されたノードを削除すると、新しい最大回転数になります。）

最悪の場合のAVL木

于 2012-12-26T01:08:14.953 に答える
1

私は証明が苦手で、以下は穴だらけだと思いますが、何か前向きなことになるかもしれません。

ノードの削除後に最小化されたAVLツリーでk回転を実行するには、次の条件が満たされている必要があります。

  • ターゲットノードは、4ノードのサブツリーに存在する必要があります。
  • ターゲットノードは、短いブランチ上にあるか、サブツリーのルートであり、短いブランチのリーフに置き換えられている必要があります。
  • ターゲットサブツリーのルートの祖先の各ノードは、わずかにバランスが崩れている必要があります（バランス係数は+/- 1）。つまり、バランス係数が0になると、回転チェーンが停止します。

最小化されたツリーのノードの高さと数は、次の式で計算されます。

  • H（k）=k回転の影響を受ける木の最小の高さとします。

    H(k) = 2k + 1, k > 0

  • N（h）=高さhの（最小ノード）AVLツリー内のノード数とします。

    N(0) = 0
N(1) = 1
N(h) = N(h-1) + N(h-2) + 1, h > 1

  • F（k）=k回転の影響を受けるツリー内のノードの最小数とします。

    F(k) = N(H(k))

（例えば：）

k = 1, H(k) = 4, N(4) = 7
k = 2, H(k) = 6, N(6) = 20

証明（それがそうであるように）

最小の高さ

削除すると、ノードが4つ以上あるツリーのローテーションのみが発生します。

  • 1ノードのツリーのバランス係数は0である必要があります。
  • 2ノードのツリーのバランス係数は+/-1である必要があり、削除すると1ノードのバランスツリーになります。
  • 3つのノードのツリーのバランス係数は0である必要があります。ノードを削除すると、バランス係数は+/- 1になり、回転は発生しません。
  • したがって、ノードが4つ未満のツリーから削除しても、ローテーションは発生しません。

削除時に1回転が発生する最小のサブツリーは、高さが3の4ノードです。短辺のノードを削除すると、回転が発生します。同様に、ルートノードを削除し、短辺のノードを置き換えとして使用すると、ローテーションが発生します。ツリーがどのように構成されているかは関係ありません。

  B        B     Removal of A or replacement of B with A               
 / \      / \    results in rotation. No rotation occurs
A   C    A   D   on removal of C or D, or on replacement 
     \      /    of B with C.
      D    C     

    C      C     Removal of D or replacement of C with D
   / \    / \    results in rotation. No rotation occurs
  B   D  A   D   on removal of A or B, or on replacement
 /        \      of C with B. 
A          B

4ノードツリーから削除すると、高さ2のバランスの取れたツリーになります。

  .
 / \
.   .

2番目の回転を実行するには、ターゲットツリーの兄弟の高さが4である必要があります。これにより、ルートのバランス係数は+/- 1になります（したがって、高さは5になります）。影響を受けるツリーが親の右側にあるか左側にあるかは関係ありません。また、兄弟ツリーのレイアウトも重要ではありません（つまり、H4のH3の子は左側または右側にあり、次のいずれかになります。上記の4つの向きですが、H2の子は2つの可能な向きのいずれかになります-これは証明する必要があります）。

   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

3番目のローテーションでは、影響を受けるツリーの祖父母が同様に+/- 1だけ不均衡である必要があり、4番目のローテーションでは曽祖父母が+/-1だけ不均衡である必要があることは明らかです。

定義上、サブツリーの高さは、各ブランチの最大の高さにルートの1を加えたものです。ルートで+/-1の不均衡を実現するには、一方の兄弟の身長をもう一方の兄弟より1高くする必要があります。

H(1) = 3 (as observed above)
H(k) = 1 + max(H(k - 1), H(k - 1) + 1)) = 1 + H(k - 1) + 1 = H(k - 1) + 2
... Inductive proof leading to H(k) = 2k + 1 eludes me.
最小ノード
  • 定義上、サブツリー内のノード数は、左側のブランチのノード数に右側のブランチのノード数を加えたものにルートの1を加えたものです。
  • また、定義として、高さ0のツリーには0ノードが必要であり、高さ1のツリーにはブランチがなく、したがって1ノードが必要です。
  • 一方のブランチはもう一方よりも短くなければならないことが上に示されました。

  • N（h）=高さhのツリーを作成するために必要なノードの最小数とします。

    N(0) = 0
N(1) = 1
// the number of nodes in the two subtrees plus the root
N(h) = N(h-1) + N(h-2) + 1

当然の結果

  • 大きなツリーでは、ノードの最小数が必ずしも最大であるとは限りません。ウィットに：

次のツリーからAを削除し、回転しても高さが変わらないことを確認します。したがって、親のバランス係数は変更されず、追加のローテーションは発生しません。

  B          B           D
 / \          \         / \
A   D    =>    D   =>  B   E  
   / \        / \       \    
  C   E      C   E       C

ただし、k = 2の場合、ここでH（4）が最小化されているかどうかは関係ありません。2番目の回転は引き続き発生します。

   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

質問

  • ターゲットサブツリーの位置は何ですか？明らかに、k = 1の場合はルートであり、k = 2の場合、ルートのバランス係数が-1の場合は左、それ以外の場合は右です。k> = 3の位置を決定するための式はありますか？
  • k回転を実行するためにツリーに含めることができる最大ノードはいくつですか？親がローテーションされていても、ローテーションされていない中間ノードを祖先に持つことは可能ですか？
于 2012-12-12T21:49:25.107 に答える