data-structures - スプレーツリーの代わりに2-3-4ツリーを使用する

Question

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

Answer 1

2-3-4ツリーは挿入と削除の構造のみを変更しますが、スプレーツリーは検索時にノードを再編成します。

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

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