最も効率的なデータ構造：高速ソート挿入、最も近い値基本的に

Question

を検索：

• 高速、ソートされた挿入。
• アイテムがデータ構造内に見つからない場合、そのアイテムが挿入される場所の位置を返します。

バイナリ検索の配列は私の2番目の要件を満たしていますが、それでも挿入が非常に遅いです。どのようなソリューションが最も効果的でしょうか？

Answer 1

Red-black treesおよびskip listsなどが要件を満たしています。 C++の例については、std :: set、std :: mapなど、lower_/upper_boundおよびequal_rangeメソッドを見てください。

Answer 2

多くの検索ツリーのフレーバーが要件に合っています。もし私が怠惰な気がしていたら、私は2-3の木を使うか、もしかするとひどいかもしれません。

Answer 3

バイナリ検索ツリーです。