2

私は AVL ツリーに関する文献を読んでいますが、AVL ツリーの挿入/削除で必要なバランス チェックの数についてはあまり詳しく説明されていません。

たとえば、ノードを挿入した後、新しいノードからルートまでのバランスをチェックする必要がありますか? それとも、ローテーションがコミットされた後に停止できますか?

左のサブツリーの一番右のノードをコピーするという戦略での削除はどうでしょうか? 新しく削除された (左側のサブツリーの一番右のノード) ノードからルートまで調べますか? ローテーションがコミットされた後に停止できますか?

4

2 に答える 2

1

挿入後、各「親」のバランス係数をツリーのルートまでずっと更新する必要があります。したがって、最大 O(log n) 回の更新です。ただし、ツリーを不変条件に戻すには、再構築を 1 回行うだけで済みます。

削除後、挿入と同様に、ツリー全体でバランス係数を更新する必要があります。繰り返しますが、O(log n) の更新です。ただし、挿入とは異なり、ツリーを不変条件に復元するために複数の再構築ローテーションが必要になる場合があります。

http://en.wikipedia.org/wiki/AVL_tree

于 2013-11-01T01:48:34.660 に答える
-1

もう少し詳しく調べてみたところ、いつチェックをやめればよいかわかりました。

  • 挿入したノードの上位ノードのバランス係数が0の場合。
  • 回転後。これは前回のアファメーションの結果です。

http://www.superstarcoders.com/blogs/posts/effective-avl-tree-in-c-sharp.aspx

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

于 2016-01-23T12:47:31.313 に答える