AVLツリーとスプレイツリーの違い

Question

私は様々なツリーについて勉強しており、AVLツリーとスプレイツリーに出くわしました。知りたい

1. AVLツリーとスプレイツリーの違いは何ですか？
2. どのような基準でこれらの毛束を選択しますか？
3. これらの木の肯定的なものと否定的なものは何ですか？
4. big O表記の観点から、これらのツリーのパフォーマンスはどのようなものですか？

Answer 1

1. 両方スプレー木とAVL木は、優れた性能を保証して二分探索木ですが、彼らは、彼らがその性能を保証それらを達成する方法が異なります。 AVLツリーでは、木の形状が常に拘束されているため、木の高さは決してO（log n）を超えないようになっています。このシェイプは挿入と削除時に保持され、ルックアップ時に変更されません。一方、スプレッドツリーは、それに対するルックアップに応答してツリーを再形成することによって効率的に維持される。こうすることで、頻繁にアクセスされる要素がツリーの上に移動し、参照時間が向上します。スプレイツリーの形状は制約されず、実行されるルックアップに基づいて変化します。

2. これについては固くて速いルールはありません。しかし、構造間の主な違いの1つは、AVLツリーが各操作で高速検索（O（log n））を保証し、スプレイツリーはn回の操作のシーケンスが最大でO（n log n）時間しかかからないことを保証することです。つまり、リアルタイムルックアップが必要な場合は、AVLツリーが優れている可能性があります。しかし、スプレイツリーは平均ではるかに高速になる傾向があります。したがって、ツリールックアップの実行時間を最小限に抑えたい場合は、スプレイツリーの方が優れている可能性があります。さらに、スプレイツリーは、非常に効率的に分割やマージなどの操作をサポートしていますが、対応するAVLツリー操作はより複雑で効率的ではありません。 Splayツリーは、ノードにバランス情報を格納する必要がないため、AVLツリーよりもメモリ効率が優れています。しかし、AVLツリーは、スプレイツリーでは実行できない間に、AVLツリーのルックアップを並行して実行できるため、ルックアップの多いマルチスレッド環境ではより便利です。スプレッドツリーはルックアップに基づいて再構成されるため、ツリーの要素の小さなサブセットにアクセスする必要がある場合や、他の要素よりもはるかに多くの要素にアクセスする必要がある場合、スプライトツリーはAVLツリーより優れています。最後に、スプライトツリーは、AVLツリーより実装が容易な傾向があります。これは、回転ロジックがはるかに簡単なためです。

3. 見る（2）

4. AVLツリー挿入、欠失、およびルックアップは、それぞれO（ログn）の時間がかかります。スプレッドツリーはこれらの同じ保証を持っていますが、保証は償却された意味でしかありません。すべての長い操作シーケンスは、最大でO（n log n）時間かかるだけですが、個々の操作にはO（n）回かかることがあります。

希望します。ここで

Answer 2

1）AVLツリーとスプレイツリーの違いは何ですか？

これらの構造と動作は、類似しています。相違点は、それぞれの操作の後にスプレーツリーで、ツリーをほぼ完全にバランスさせて、将来の操作にかかる時間を短縮することです。

2）どのような基準でこれらの毛束を選択しますか？

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

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

3）これらの木は肯定的で否定的ですか？

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

前述したように、スプレイツリーは多数の操作にわたって平均log（n）を持ちます。これは、おそらく、そのセット内で少なくとも1回、操作のn時間の複雑さがあることを意味します。しかし、これは頻繁なアイテムにアクセスするときに補償されます。

バイナリ検索ツリーの否定は、あなたは常にlog（n）を持つことが幸運である必要があるということです。キーがランダムでない場合、ツリーは片面のみのフォームのようなリストに縮小されます。

4）大きなO表記の観点から、これらのツリーのパフォーマンスはどうですか？

Splay treeツリー操作のグループの平均Log（n）。 バイナリツリーキーがランダムに発生している場合にのみログに記録されます（n）。

実行時の結果はここではっきりしていますsplay tree runtime profiling 実行時の違いは、スプレッドの有無にかかわらず検索できます。