二分探索木がどのように実装されているかは理解していますが、ほとんどのプログラミング言語が標準ライブラリに組み込んでいるハッシュテーブルよりも二分探索木を使用する利点が何であるかわかりません。
誰かが二分探索木で解決できる現実の問題の例を提供してもらえますか？
6901 次
5 に答える
31
ハッシュテーブルに対する二分探索木の理論上の利点はいくつかあります。
要素をソートされた順序で格納します。これは、ソートされた順序で値に簡単にアクセスできる方法でコンテナを格納する場合は、ハッシュテーブルよりもBSTの方がおそらく適切な選択であることを意味します。たとえば、学生のコレクションを保存してから、すべての学生をアルファベット順に印刷する場合は、ハッシュテーブルよりもBSTの方がはるかに適しています。
範囲クエリを効率的にサポートします。BSTは並べ替えられた順序で保存されるため、「[x、y]の範囲の値は何ですか？」という形式の質問に簡単に答えることができます。二分探索木で。これを行うには、ツリー内でxより大きい最小要素とyより小さい最大要素を検索し、それらの間のツリーの要素を反復処理します。これらのクエリは両方ともバランスの取れたツリーでO（lg n）時間で実行されるため、この操作の合計実行時間はO（lg n + k）です。ここで、kはクエリに一致する要素の数です。
これらは、最近傍のクエリを効率的にサポートします。 ハッシュテーブルは、わずかに異なる場合でも大きく異なるハッシュコードを生成するように特別に設計されています。これにより、ハッシュ値に、1つのスポットに多くの要素がクラスター化されないようにするために必要な分散が与えられます。ただし、これは、探しているものに「近い」可能性のある要素を見つけるために、ハッシュテーブルに対して線形スキャンを実行する必要があることも意味します。BSTを使用すると、ツリーにない場合でも、任意の値の先行および後続を効率的に見つけることができます。
彼らはより良い最悪の場合の保証を持つことができます。ほとんどのハッシュテーブルの実装には、最悪の場合に操作がO（n）に低下する可能性があるある種の縮退したケースがあります。線形プロービングハッシュテーブルまたはチェーンハッシュテーブルは、要素のセットが不適切な場合、ルックアップごとにO（n）時間を必要とするか、再ハッシュでO（n）時間を必要とする可能性があります。赤/黒木、AVL木、AA木など、一部のタイプのバランスの取れたBSTへの挿入は、常に最悪の場合のO（lg n）です。
BSTをより複雑なツリー構造に一般化する場合は、ハッシュテーブルよりもはるかに効率的に問題を解決するためにツリーを使用できる多くのアプリケーションがあります。次にいくつかの例を示します。
kd-treesを使用すると、多次元空間での高速範囲クエリと効率的な最近傍ルックアップをサポートしながら、多次元データを格納できます。それらを分類（怠惰な学習アルゴリズム）または計算幾何学に使用できます。
リンク/カットツリーを使用すると、ほとんどの従来のアルゴリズムよりもはるかに効率的に最大フロー問題を解決できます。優れたプッシュ/再ラベル付けアルゴリズムは、これを使用して実装を高速化します。
素集合フォレストを使用して、要素のパーティションを可能な限り漸近的に効率的に維持できます（更新ごとに償却されたα（n）、ここでα（n）はアッカーマン逆関数です）。これらは、多くの高速最小スパニングツリーアルゴリズム、およびいくつかの最大マッチングアルゴリズムで使用されます。
バイナリヒープを使用して、優先キューを効率的に実装できます。より複雑なツリーを使用して、理論計算機科学で非常に重要な二項ヒープとフィボナッチヒープを構築できます。
決定木は、分類のための機械学習で使用でき、理論計算機科学のモデルとして使用して、さまざまなアルゴリズムの実行時間の限界を証明できます。
三分探索木は、わずかに変更されたBSTに基づく試行の代替手段です。それらは非常に高速な要素の検索と挿入を可能にし、まばらなデータセットは非常に簡潔です。
Bツリーは、ディスクアクセスが制限要因である要素を効率的に検索するために、多くのデータベースシステムで使用されています。
バイナリ空間分割ツリーは、コンピュータグラフィックスをすばやくレンダリングし（元のゲームDoomでレンダリングを最適化するために使用されました）、衝突検出を行うために使用できるkdツリーの一般化です。
BKツリーを使用すると、他の単語から特定の編集距離内にあるすべての単語をすばやく判別できます。より一般的には、他の点から特定の距離内にある距離空間内のすべての点を見つけることができます。
フュージョンツリーは、ルックアップ、挿入、および削除を非常に高速にサポートする整数キーのハッシュテーブルの代替手段です。
van Emde Boasは、要素ごとのO（lg lg n）時間でルックアップ、挿入、削除、後続、および先行をサポートする整数キーのハッシュテーブルの別の代替手段をツリー化します。一部のデータベースシステムは、パフォーマンスを最適化するためにvEBツリーを使用します。
この答えがどれほど話題になっているのかはわかりませんが、BSTとより一般的なツリー構造がどれほど素晴らしく強力であるかを理解できるはずです。
于 2011-02-16T00:05:29.443 に答える
1
バイナリツリーが必要な例の1つは、コンピュータグラフィックスのバイナリスペースパーティションです。
http://en.wikipedia.org/wiki/Binary_space_partitioning
アルゴリズムでは二分木のノード間の関係を保持する必要があるため、二分木が必要です。ツリーの構造が重要なアルゴリズムは他にもたくさんあるため、ハッシュテーブルは適切な構造ではありません。
ハッシュテーブルの代わりにバイナリツリーを使用するもう1つの理由は、データアイテムの効率的なハッシュを簡単に生成できないが、比較関数を生成できる場合です。
多くの場合、データの単純な保存と取得には、ハッシュテーブルの方が最適ですが、実装はより複雑です。
于 2011-02-15T23:53:30.240 に答える
0
最も見過ごされているのは、多くのファイルシステムがバイナリツリーを使用してディレクトリリストを管理していることです。プレーンなバイナリツリーを使用することはめったにありませんが、Bツリーなどのバリエーションがあります。これは、ツリーのディスク上のストレージの問題が実装の詳細にとって非常に重要であるためです。彼らがこの種の構造を使用する理由は、効率とスピードのためです。これにより、ディレクトリ内の何千ものファイルをサポートするなどのことが可能になります。ファイルの作成時間と削除時間の比較により、ファイルシステムのこの側面の効率が浮き彫りになります。
二分木は、3Dオブジェクトをレンダリングする多くのゲームでも使用されます。繰り返しますが、その理由はスピードです。実際、速度は非常に重要であるため、Quakeエンジンなどの一部のゲームエンジンでは、マップビルドプロセスの一部としてバイナリツリーが事前に生成され、事前に最適化されています。
于 2011-02-15T23:56:41.517 に答える
0
注意すべきことの1つは、二分探索木はスペース効率が良いということです。たとえば、格納する整数が10個あり、0〜99の範囲でマップされるハッシュ関数がある場合、uには100個の整数の配列が必要です。二分探索木を使用した場合、10個の要素に必要な量のメモリのみを割り当てます。
于 2011-02-15T23:57:49.750 に答える
0
これはおそらくコメントであるはずですが、BSTではなく自己平衡BST（s）（log（n））が広く使用されています。プレーンBSTには、最悪の場合のO（N）挿入/削除時間があります。
于 2011-02-16T02:14:19.943 に答える