52

いろいろな木を勉強していて、AVL木やスプレー木に出くわしました。私は知りたいです

  1. AVLツリーとスプレーツリーの違いは何ですか？
  2. これらの房をどのような基準で選択しますか？
  3. これらの木のポジティブとネガティブは何ですか？
  4. これらの木のパフォーマンスは、大きなO表記でどのようになっていますか？
4

2 に答える 2

93

あなたの質問に答えるには：

  1. AVLツリーとスプレーツリーの違いは何ですか？スプレーツリーとAVLツリーはどちらも、優れたパフォーマンス保証を備えた二分探索ツリーですが、パフォーマンスを保証する方法が異なります。AVLツリーでは、ツリーの形状が常にバランスが取れるように制約されます。つまり、ツリーの高さがO（log n）を超えることはありません。この形状は、挿入と削除で維持され、ルックアップ中に変更されません。一方、スプレーツリーは、ルックアップに応じてツリーを再形成することにより、効率を維持します。そうすることで、頻繁にアクセスされる要素がツリーの最上部に向かって移動し、ルックアップ時間が短縮されます。スプレー木の形状は制約されておらず、実行されるルックアップによって異なります。

  2. これらの木はどのような基準で選択しますか？これについての厳格なルールはありません。ただし、構造間の重要な違いの1つは、AVLツリーは各操作で高速ルックアップ（O（log n））を保証するのに対し、スプレーツリーはn個の操作のシーケンスが最大でO（n log n）時間かかることのみを保証できることです。つまり、リアルタイムのルックアップが必要な場合は、AVLツリーの方が優れている可能性があります。ただし、スプレーツリーは平均してはるかに高速である傾向があるため、ツリールックアップの合計実行時間を最小限に抑えたい場合は、スプレーツリーの方が優れている可能性があります。さらに、スプレーツリーは分割やマージなどの一部の操作を非常に効率的にサポートしますが、対応するAVLツリー操作はより複雑で効率が低くなります。スプレーツリーは、ノードにバランス情報を格納する必要がないため、AVLツリーよりもメモリ効率が高くなります。でも、AVLツリーは、スプレーツリーでは実行できないのに対し、AVLツリーでのルックアップは並行して実行できるため、ルックアップが多いマルチスレッド環境でより役立ちます。スプレーツリーはルックアップに基づいて形を変えるため、ツリーの要素の小さなサブセットにのみアクセスする必要がある場合、または一部の要素に他の要素よりもはるかに多くアクセスする場合、スプレーツリーはAVLツリーよりもパフォーマンスが高くなります。最後に、回転ロジックがはるかに簡単なため、スプレーツリーはAVLツリーよりも実装が簡単になる傾向があります。スプレーツリーはAVLツリーよりもパフォーマンスが優れています。最後に、回転ロジックがはるかに簡単なため、スプレーツリーはAVLツリーよりも実装が簡単になる傾向があります。スプレーツリーはAVLツリーよりもパフォーマンスが優れています。最後に、回転ロジックがはるかに簡単なため、スプレーツリーはAVLツリーよりも実装が簡単になる傾向があります。

  3. これらの木の良い点と悪い点は何ですか？上記（2）に対する私の答えを参照してください。

  4. これらの木のパフォーマンスは、big-O表記でどのようになっていますか？AVLツリーの挿入、削除、およびルックアップには、それぞれO（log n）時間がかかります。スプレー木にも同じ保証がありますが、保証は償却された意味でのみです。長い一連の操作には最大でO（n log n）時間がかかりますが、個々の操作にはO（n）時間かかる場合があります。

お役に立てれば！

于 2012-02-04T22:06:39.363 に答える
2
  1. AVLツリーとスプレーツリーの違いは何ですか？

それらは構造と私たちがそれらに要求する操作において類似しています。違いは、スプレーツリーでは、各操作の後に、ツリーをほぼ完全にバランスさせて、将来の操作にかかる時間を短縮しようとすることです。

  1. これらの房をどのような基準で選択しますか？

アプリケーションがツリー内の大量のデータを処理するが、他のデータよりも頻繁にデータのサブセットにアクセスする必要がある場合、スプレーツリーは常にバイナリ検索ツリーよりも優れています。この場合、頻繁にアクセスするデータは、スプレイの結果としてルートの近くに来ます。また、以前よりも短い時間で任意のノードにアクセスできます。

これらのツリーを選択するための一般的なルールとして、ツリー操作の期間にわたって「平均」log（n）時間が必要な場合は、スプレーツリーを使用します。二分木はこれを保証できません。

  1. これらの木のポジティブとネガティブは何ですか？

両方の利点は、理論的には、これらの両方のデータ構造でlog（n）を回避できることです。

前述のように、スプレー木は多くの操作にわたって平均log（n）を持っています。つまり、そのセットで少なくとも1回は、操作がn時間複雑になる可能性があります。ただし、これは頻繁なアイテムにアクセスするときに補正されます。

二分探索木の欠点は、常にlog（n）を持つことが幸運である必要があるということです。キーがランダムでない場合、ツリーは片側だけのフォームのようなリストになります。

  1. これらの木のパフォーマンスは、大きなO表記でどのようになっていますか？

キーがランダムに移動する場合にのみ、ツリー操作のグループのスプレーツリーLog（n）を平均します。バイナリツリーLog（n）。

ランタイムでの結果はここで明らかです。スプレイがある場合とない場合の検索の実行時の違いを確認できます。

于 2012-01-18T03:40:56.683 に答える