arrays - 高效的数据结构，用于快速随机访问、搜索、插入和删除

Question

我正在寻找一种数据结构(或多个结构)，它可以让我保留一个有序的整数列表，没有重复项，并且索引和值在同一范围内。

我需要四个主要操作才能高效，按重要性的粗略顺序排列:

1. 从给定索引中获取值
2. 查找给定值的索引
3. 在给定索引处插入值
4. 删除给定索引处的值

使用数组，我的 1 的复杂度为 O(1)，但 2 的复杂度为 O(N)，并且插入和删除的成本很高(我相信也是 O(N))。

链表的插入和删除时间复杂度为 O(1)(一旦有了节点)，但 1 和 2 的时间复杂度为 O(N)，因此抵消了增益。

我尝试保留两个数组 a[index]=value 和 b[value]=index，这将 1 和 2 变成 O(1)，但将 3 和 4 变成成本更高的操作。

是否有更适合于此的数据结构？

Answer 1

我会使用red-black tree将键映射到值。这为您提供了 1、3、4 的 O(log(n))。它还按排序顺序维护键。

对于 2，我将使用哈希表将值映射到键，这将为您提供 O(1) 性能。它还增加了 O(1) 开销，用于在红黑树中添加和删除键时保持哈希表更新。