为快速随机访问，搜索，插入和删除有效的数据结构 [英] Efficient data structure for fast random access, search, insertion and deletion
问题描述
我在寻找一个数据结构（或结构），让我让我的整数，没有重复的有序列表，在同一个范围索引和值。
I'm looking for a data structure (or structures) that would allow me keep me an ordered list of integers, no duplicates, with indexes and values in the same range.
我需要四个主要的业务是有效的，按重要性顺序粗糙：
I need four main operations to be efficient, in rough order of importance:
- 从给定索引取值
- 找到一个给定值的指数
- 一个给定的索引处插入一个值
- 一个给定的索引处删除值
在使用O（1）数组我有1，但2 O（N）和插入和删除是昂贵的（O（N），以及，我相信）。
Using an array I have 1 at O(1), but 2 is O(N) and insertion and deletions are expensive (O(N) as well, I believe).
一个链表为O（1）插入和删除（一旦你的节点），但1和2是O（N），从而否定了收益。
A Linked List has O(1) insertion and deletion (once you have the node), but 1 and 2 are O(N) thus negating the gains.
我试图保持两个数组A [指数] =价值和b [值] =指数，它转动1和2成O（1），但把3和4成甚至更昂贵的操作。
I tried keeping two arrays a[index]=value and b[value]=index, which turn 1 and 2 into O(1) but turn 3 and 4 into even more costly operations.
有一个数据结构，这更适合？
Is there a data structure better suited for this?
推荐答案
我会用一个红黑树到键映射到值。这给了你1 O（日志（N）），3，4，它也保持在排序顺序按键。
I would use a red-black tree to map keys to values. This gives you O(log(n)) for 1, 3, 4. It also maintains the keys in sorted order.
有关2，我会用一个哈希表值映射到按键，它给你O（1）性能。它还增加了O（1）开销保持更新，添加和在红黑树删除键时，哈希表。
For 2, I would use a hash table to map values to keys, which gives you O(1) performance. It also adds O(1) overhead for keeping the hash table updated when adding and deleting keys in the red-black tree.
这篇关于为快速随机访问，搜索，插入和删除有效的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
