インデックスとキーによるランダムアクセスをサポートしているデータ構造、順序が維持された状態でlogaritmic時間での挿入、削除

Question

私はE =（K、V）要素の順序付きリストを格納するデータ構造を探しており、多くてもO（log（N））時間であり、Nは要素の数である。メモリ使用量は問題ではありません。

• Eは（インデックス）//はインデックス
• int型のfind（K）で要素を取得// K一致し
• （インデックス）//がインデックスにある要素を削除し、削除要素のインデックスを見つけます、次の要素は、そのインデックスは、インデックスにある要素を挿入する// 1つの
• 挿入（イ​​ンデックス、E）減少しており、以下の要素がそのインデックスは、私は、次の間違った解決策を検討している1

増加しています

• 使用アレイ：find、delete、及びinsert意志依然としてO（N）
• 使用アレー+インデックスKのマップ：deleteとinsertは依然としてO（N）の費用がかかりますマップ
の要素をシフトし、更新します
• 使用は、エレメントアドレスをリスト+ Kのマップをリンク：getとfindはまだ私の想像ではO（N）

の費用がかかります、最後の解決策が最も近いですが、代わりにリンクされたリストの、自己均衡ツリー各ノードが左にある要素の数を格納すると、getをO（log（N））で実行できるようになります。

私は正しいかどうか分からないので、私の想像力が正しいかどうか、この種のデータ構造の名前があるかどうかを尋ねたいと思いますので、既製のソリューションを探すことができます。

Answer 1

私が考えることができる最も近いデータ構造はtreapsです。

暗黙のトレバーは、非常に強力なデータ構造である通常のトレップの単純な変更です。

1. 任意の位置での配列の要素を挿入する：実際には、暗黙treapは（全部でO（logN個）O（log⁡N）にはオンラインモード）に実装以下の手順アレイとして考えることができます
2. 任意の間隔
3. 添加オン等和、最小/最大の要素を見つける任意の要素
4. の除去、任意の間隔

の要素を逆に任意の間隔

上の絵

暗黙のキーによる変更を使用すると、2番目のキー以外のすべての操作を実行できます（Kが一致する要素のインデックスを見つける）。

Answer 2

要件に基づいてヒープを維持することができます。