スプレイツリーの代わりに2-3-4ツリーを使用

Question

私はデータ構造のコースにいます。私たちは2-3-4ツリーとスプレーツリーについて学習しました。どのような状況でスプレイツリーの代わりに2-3-4ツリーを使用したいと思っていましたか？彼らは自己バランスとソートの両方をしているので、私はそれらの違いの多くを見ていない。

Answer 1

2-3-4 treeは、挿入と削除時に構造を変更するだけで、splay-treeは検索時にノードを再構成します。

一般的な使用パターンがほとんどの場合、要素の小さなサブセットを検索した場合、スプレイツリーはルックアップの再構成のおかげでより高速な応答を提供します。

最小の要素をO（1）でルックアップできるように2-3-4ツリーを実装することは可能ですが、一般に、償却されたO（log n）で挿入と削除が行われます。