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

Question

我正在寻找一个数据结构(或结构),这将允许我保持一个有序的整数列表,没有重复,索引和值在同一范围内.

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

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

使用数组我在O(1)处有1,但是2是O(N)并且插入和删除是昂贵的(O(N),我相信).

链接列表具有O(1)插入和删除(一旦有了节点),但是1和2是O(N),因此否定了增益.

我尝试将两个数组保持为[index] = value和b [value] = index,将1和2转换为O(1),但将3和4转换为更昂贵的操作.

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

Answer 1

我会使用红黑树将键映射到值.这为您提供了1,3(4)的O(log(n)).它还按排序顺序维护键.

对于2,我会使用哈希表将值映射到键,这样可以获得O(1)性能.它还增加了O(1)开销,用于在红黑树中添加和删除键时保持哈希表的更新.