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

Question

私は現在、データ構造コースにいますが、2〜3-4の木と広がりの木について学びました。私は、どのような状況でスプレーツリーの代わりに2-3-4ツリーを使用するのだろうと思っていましたか？彼らは両方とも自己バランスをとっていてソートされているので、私はそれらの間にそれほど大きな違いは見られません。

Answer 1

a 2-3-4ツリー 挿入と削除の構造を変更するだけで、 スプレーツリー また、検索でノードを再編成します。

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

2-3-4ツリーを実装して、最小の要素をO（1）で検索できるようにすることができますが、通常、両方とも償却o（log n）で挿入と削除を提供します。