用于快速随机访问、搜索、插入和删除的高效数据结构 [英] 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:

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

使用数组我在 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[index]=value 和 b[value]=index，它们将 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?

推荐答案

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

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