快速随机访问，搜索，插入和删除的高效数据结构 [英] Efficient data structure for fast random access, search, insertion and deletion

问题描述

我正在寻找一个数据结构（或结构），允许我保持一个有序的整数列表，没有重复的索引和值在同一个范围内。

我需要四个主要操作，以高效的方式，重要性很重要：

1. 从给定的索引获取值
2. 
   
3. 找到给定值的索引


4. 在给定索引处插入一个值


5. 删除一个值给定索引

使用数组我在O（1）有1，但2是O（N），插入和删除是昂贵的（O（N）），我相信）。

链接列表具有O（1）插入和删除（一旦拥有节点），但1和2是O（N），从而否定了收益。 p>

我尝试保留两个数组a [index] = value和b [value] = index，将1和2转换为O（1），但将3和4转换为更多

有没有更好的数据结构？

解决方案

我将使用红黑树将键映射到值。这给你的O（log（n））为1，3，4.它还按排序顺序维护密钥。

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

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:

1. taking the value from a given index
2. finding the index of a given value
3. inserting a value at a given index
4. deleting a value at a given index

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).

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.

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?

解决方案

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.

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屋！