1

DSWアルゴリズムまたは赤黒バランスツリーを使用して、任意の二分探索木を前処理して完全な二分木に変換できることを私は知っています。

これらの 2 つの方法は、時間の複雑さに関してどのように異なるのでしょうか?

ある方法を他の方法ではなく使用する利点を示す例/アプリケーションをそれぞれ提供できますか。

4

2 に答える 2

1

DSWは静的アルゴリズムです。一度使用すると、ツリーが変更されないことが期待されます。ツリーを完全にバランスさせるにはO（N）時間がかかります。その後、それを使用できますが、変更しないことが期待されます。それでもそれは可能ですが、完全にバランスが取れているという特性は失われます。変更操作が多いほど、ツリーのパフォーマンスは低下します。

赤黒木は動的なデータ構造です。基本的な操作はO（log（N））で実行されますが、もちろん、完全にバランスの取れたツリーほどうまく機能しません。最も重要なのは、赤黒木がフライドで変更される可能性があり、それでも操作にO（log（N））が必要になることです。

したがって、2つのアプローチはユースケースが異なります。お役に立てれば。

于 2013-01-02T13:49:06.790 に答える
0

DSW は、BST 全体 (アンバランス) を作成してから、(バランス後の BST で) 多数のルックアップを実行する場合に便利です。RB ツリーは、追加/削除/検索がすべて織り交ぜられている場合に便利です。

RB ツリーはほとんどバランスが取れていますが、DSW は完全なバイナリ ツリーです (おそらく最後のレベルを除く)。

どちらも O(log n) を提供しますが、DSW は償却可能な 1 回限りの操作です。

于 2013-01-02T13:46:56.150 に答える