インデックスによる素早い要素の挿入/削除のための最良のデータ構造（コンテナ）は何ですか？

Question

インデックスによる高速要素挿入/削除のための最良のデータ構造（コンテナ）は何ですか？

Answer 1

：

struct Node<T> 
    T value 
    Node left 
    int left_count 
    Node right 
    int right_count 
end 

がleft_count値がツリーのleftブランチ内のノードの数を保持するだろう、と同様に右側のルックアップは、ツリーの先頭から開始し、所望のインデックス値を左右のカウントと比較して下方に移動することによって実行される。挿入と削除は、カウント値を適切に調整して、通常のバイナリツリーアルゴリズムを使用して実行されます。バイナリツリーのバランスを取ることを要求することにより、より一貫したパフォーマンスを達成することができます。

この種のツリーにはおそらく名前があります。より多くの情報を感謝！

Answer 2

あなたがメモリ内またはディスク内の何かについて話しているかどうかによって異なります。通常、ディスク上にはBツリーのいくつかの変形があり、通常はメモリ内にリンクされています（挿入する必要のあるノードがわかっている場合）。

Answer 3

固定間隔で動的にサイズ変更されるハッシュテーブルを試してください。

かなり均一な分布を仮定すると、は基本的に一定時間[O（1）]アクセス時間になるはずです。

http://www.cs.cornell.edu/courses/cs312/2006fa/lectures/lec14.html

そのリンクは良い説明を与えるように思われます。あなたはO（Nログ）は、このようなノード構造の二分木を使用してパフォーマンス得ることができる