6

我面临一个应用程序，我必须设计一个具有随机访问（或至少比 O(n) 更好）的容器具有便宜的 (O(1)) 插入和删除，并根据顺序存储数据（等级) 在插入时指定。

例如，如果我有以下数组：

[2, 9, 10, 3, 4, 6]

我可以调用索引 2 上的 remove 来删除 10，我也可以通过插入 13 来调用索引 1 上的 insert。

在这两个操作之后，我将拥有：

[2, 13, 9, 3, 4, 6]

这些数字存储在一个序列中，插入/删除操作需要一个索引参数来指定应该在哪里插入数字或应该删除哪个数字。

我的问题是，除了链表和向量之外，什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的堆。但我一直看到一些关于融合树有用的东西（但更多的是理论上的意义）。

什么样的数据结构可以给我最佳的运行时间，同时还能降低内存消耗？我一直在玩一个保留插入顺序的哈希表，但到目前为止它一直没有成功。

我直接使用 std:: 向量的原因是因为我必须构造一些东西，根据这些基本操作预先形成向量。容器的大小有可能增长到数十万个元素，因此在 std::vector 中进行转换是不可能的。与链表相同的问题（即使是双链表），在最坏的情况下遍历它到给定的索引将需要 O (n/2)，它被舍入到 O (n)。

我正在考虑一个包含 Head、Tail 和 Middle 指针的双向链表，但我觉得不会好多少。

4

2 回答 2

7

在基本用法中，为了能够在任意位置插入和删除，可以使用链表。它们允许 O(1) 插入/删除，但前提是您已经在列表中找到要插入的位置。您可以在“给定元素之后”插入（即，给定一个指向元素的指针），但不能有效地插入“在给定索引处”。

为了能够在给定索引的情况下插入和删除元素，您将需要更高级的数据结构。我知道至少存在两种​​这样的结构。

一种是绳索结构，它在一些 C++ 扩展（SGI STL或 GCC via #include <ext/rope>）中可用。它允许在任意位置插入/删除 O(log N)。

另一个允许 O(log N) 插入/删除的结构是隐式 treap（又名隐式笛卡尔树），您可以在http://codeforces.com/blog/entry/3767找到一些信息，使用隐式键进行 Treap或https： //codereview.stackexchange.com/questions/70456/treap-with-implicit-keys。

也可以修改隐式陷阱以允许在其中找到最小值（并且还支持更多操作）。不确定绳子是否可以处理这个问题。

UPD：事实上，我想您可以通过将任何 O(log N) 二叉搜索树（例如 AVL 或红黑树）转换为“隐式密钥”方案来适应您的请求。概要如下。

想象一棵二叉搜索树，它在每个给定时刻都将结果数 1、2、...、N 存储为其键（N 是树中的节点数）。每次我们更改树（插入或删除节点）时，我们都会重新计算所有存储的键，以便它们仍然从 1 到 N 的新值。这将允许在任意位置插入/删除，因为键现在是位置，但更新所有密钥需要太多时间。

为避免这种情况，我们不会在树中显式存储键。相反，对于每个节点，我们将在其子树中存储节点数。因此，任何时候我们从树根向下走，我们都可以跟踪当前节点的索引（位置）——我们只需要将我们左边的子树的大小相加。这允许我们在给定k的情况下找到索引为k的节点（即，这是二叉搜索树标准顺序中的第 k 个），在 O(log N) 时间。之后，我们可以使用标准的二叉树过程在该位置执行插入或删除；我们只需要更新在更新期间更改的所有节点的子树大小，但这很容易在每个节点更改的 O(1) 时间内完成，因此总插入或删除时间将为 O(log N)，如原始二叉搜索树。

因此，这种方法允许使用任何 O(log N) 二叉搜索树作为基础，在 O(log N) 时间内在给定位置插入/删除/访问节点。您当然可以将所需的附加信息（“值”）存储在节点中，甚至可以通过保持每个节点子树的最小值来计算树中这些值的最小值。

但是，前面提到的treap 和rope 更先进，因为它们还允许拆分和合并操作（获取子字符串/子数组并连接两个字符串/数组）。

于 2015-04-23T07:58:37.860 回答
0

考虑一个跳过列表，它可以在其“可索引”变体中实现线性时间排序操作。

对于算法（伪代码），请参阅Pugh 的 A Skip List Cookbook。

可能是上面@Petr 概述的“隐式键”二叉搜索树方法更容易获得，甚至可能表现更好。

于 2016-05-02T19:40:49.650 回答