通过索引和键支持随机访问的数据结构，在维持顺序的对数时间内插入和删除

Question

我正在查找存储E =（K，V）元素的有序列表并支持以下操作的数据结构最多为O（log（N））时间，其中N是元素的数量。内存使用不成问题。

• Ë得到（指数）的指数//获取元素
• INT查找（K）//找到元素，其ķ匹配
• 删除（指数）的指数//在索引中删除元素，以下的元件及其索引减少1个
• 刀片（指数，E）//插入在索引元件，下面的元件及其索引增加1

我已经考虑以下不正确的解决方案：

• 使用数组：find，delete，和insert仍将O（N）
• 使用阵列+ K的地图索引：delete和insert仍然将花费O（N），用于切换元件和更新地图
• 使用链接的K表+地图元素地址：get和find仍然将花费O（N）

在我的想象中，最后的解决方案是最接近的，而是链表，一个自我平衡的树每个节点在其左侧存储元素的数量将使我们可以在O（log（N））中执行get。

但是我不确定我是否正确，所以我想问一下我的想象是否正确以及是否有这种数据结构的名称，以便我可以寻找现成的解决方案。

Answer 1

我能想到的最接近的数据结构是treaps。

隐式treap是对常规treap的简单修改，这是一个非常强大的数据结构。事实上，隐式树堆可以被认为是与实施（全部在O（logN）的O（log⁡N）在在线模式）以下过程的数组：

1. 在任何位置处插入的元件阵列中的
2. 去除任意元素
3. 的上的任意间隔查找总和，最小/最大元件等
4. 加法，画上的任意间隔
5. 上的任意间隔反向元件

使用隐式键修改允许您执行除第二个键外的所有操作（查找K匹配的元素的索引）。我会编辑这个答案，如果我想出一个更好的主意:)

Answer 2

您可以根据您的要求维护一个堆阵列。