我应该为这些操作使用什么数据结构？

Question

我需要一个数据结构来存储 {1, . . . , n} (n 最初给出) 并仅支持这些操作：

• 最初：给定n，S = {1, . . . ,n}开头。

• delete(i)：从 S 中删除 i。如果 i 不在 S 中，则无效。

• pred(i)：Return i 的 S 中的前导。这意味着 max{j ∈ S | j < i}，S中最大的元素严格小于 i。如果有none, return 0.参数i保证在{1, . . . , n}, 但可能在也可能不在 S.

例如，如果 n = 7 且 S = {1, 3, 6, 7}，则 pred(1) returns 0, pred(2) 和 pred(3) return 1.

我需要弄清楚：

表示S的数据结构
初始化算法（O(n) 时间）
删除算法(O(α(n))摊销时间)
pred (O(α(n)) 摊销时间)的算法

非常感谢任何帮助（我不需要代码 - 只需要算法）。

Answer 1

我不确定是否有一种数据结构可以在 O(α(n)) 时间内保证所有这些属性，但一个好的开始是像 van Emde Boas trees or y-fast tries[=13 这样的前身数据结构=]

vEB 树的工作原理是根据元素索引的二进制表示递归定义的。让我们假设 n=2^b 对于某些 b=2^k

如果我们只有两个元素，存储最小值和最大值
否则，我们将所有元素的二进制表示分为高b/2位和低b/2位。
我们为所有元素的高位构建一棵 vEB 树 ('summary')，为低位构建 √n 个 vBE 树（高位的每个选择一个）。此外，我们存储最小和最大元素。

这为您提供了 O(n) space 的使用时间和 O(log log n) = O(k) 的搜索、插入和删除时间。
但是请注意，涉及的常数因子可能非常大。如果您的 n 在 32 位中代表 table，至少我知道 Dementiev 等人的 this report。当使用其他技术更容易解决问题规模时打破递归

y-fast 尝试的想法建立在 x-fast 尝试的基础上：
它们最简单地被描述为基于其元素的二进制表示的 trie，结合每个级别的哈希 table 和一些额外的指针。

y-fast 尝试通过将元素拆分为几乎相等大小的分区并从中选择代表（最大）来减少 space 使用，在其上构建 x-fast trie。然后使用正常的平衡搜索树实现分区内的搜索。

space 用法和时间复杂度与 vEB 相当。我猜常数因子会比 vEB 的简单实现小一点，但这个说法只是基于直觉。

最后一点：永远记住 log log n < 6，这在不久的将来可能不会改变

Answer 2

您可以使用 Disjoint-set data structure。

让我们将子集表示为不相交集。不相交集的每个元素都是子集 i 的一个元素（包括始终存在的零），与集合中大于 i 且小于下一个集合元素的所有缺失元素联合。

示例：

n = 10
s = [1, 4, 7, 8], disjoint-set = [{0}, {1,2,3}, {4,5,6}, {7}, {8, 9, 10}]
s = [3, 5, 6, 10], disjoint-set = [{0, 1, 2}, {3, 4}, {5}, {6, 7, 8, 9}, {10}]

最初，我们有一个完整的集合，由 n+1 个不相交的集合元素（包括零）表示。通常，每个不相交集元素都是一棵有根树，我们可以在每个树根的元素中存储 leftmost 数字。

设 leftmost(i) 是包含 i 的不相交集元素的 leftmost 值。

leftmost(i) 操作类似于不相交集的 Find 操作。我们只是从 i 到元素的根，然后 return 为根存储的 leftmost 数字。 复杂度：O(α(n))

我们可以检查 i 是否在比较 i 和 leftmost(i) 的子集中。如果它们相等（并且 i > 0），则 i 在子集中。

如果 i 不在子集中，

pred(i) 将等于 leftmost(i)，如果 i 在子集中，则等于 leftmost(i-1)。 复杂度：O(α(n))

在每个 delete(i) 操作中，我们首先检查 i 是否在子集中。如果 i 在子集中，我们应该将包含 i 的元素与左邻元素（这是包含 i-1 的元素）合并。此操作类似于不相交集的 Union 操作。结果树的 leftmost 数量将等于 leftmost(i-1)。 复杂度：O(α(n))

编辑：我刚刚注意到问题中的 "strictly less than i"，稍微更改了描述。

Answer 3

在提供O(α(n))的时间方面，确实比较棘手。这是我的想法：

由于我们知道i的范围是1到n，我们可以先构造一个自平衡BST，如AVL tree.这个 AVL 树的节点应该是 DataNode 的对象。它可能是这样的：
```
public class DataNode{
int value;
boolean type;
DataNode(int value, boolean type){
    this.value = value;
    this.type = type;

    }
}
```
value 将只包含 1 到 n 范围内的所有值。如果我们在树中插入的项目存在于集合 S 中，则 type 变量将被赋值为 true。否则，它将被标记为 false。

这需要 O(n) 的创建时间。删除可以在 O(logn) 时间内完成。对于 pred(i)，如果我是正确的，我们可以实现平均案例时间复杂度在 O(logn) 左右。 pred(i) 的算法应该是这样的：

在树中找到元素 i。如果 type 为 true，则 return 此元素的顺序前导 i 如果此前导的类型值为 true。
如果是false，则循环查找该元素的下一个前驱（即i-1的前驱），直到找到type = true.
如果没有找到 type = true 这样的前任，则 return 0.

我希望我们可以进一步优化这种方法，使它在 O(α(n)) 内成为 pred(i)。

我应该为这些操作使用什么数据结构？

What data structure should I use for these operations?

algorithm

data-structures

amortized-analysis