6

我需要一个数据结构来存储 {1, . . . , n}（n 最初给出）并且仅支持以下操作：

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

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

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

例如，如果 n = 7 且 S = {1, 3, 6, 7}，则 pred(1) 返回 0， pred(2) 和 pred(3) 返回 1。

我需要弄清楚：

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

将不胜感激任何帮助（我不需要代码 - 只是算法）。

4

3 回答 3

5

您可以使用不相交集数据结构。

让我们将我们的子集表示为不相交集。不相交集的每个元素都是子集的一个元素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每个树根的数字存储在元素中。

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

leftmost(i)操作类似于不相交集的查找操作。我们只是从i元素的根开始并返回leftmost为根存储的数字。复杂性：O(α(n))

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

pred(i)将等于leftmost(i)ifi不在子集中，并且等于leftmost(i-1)ifi在子集中。复杂性：O(α(n))

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

编辑：我刚刚注意到问题中的“严格小于我”，稍微改变了描述。

于 2017-07-11T08:58:00.090 回答
1

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

vEB 树的工作是基于元素索引的二进制表示递归定义的。假设对于某些 b=2^k，n=2^b

  • 如果我们只有两个元素，存储最小值和最大值

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

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

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

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

空间使用和时间复杂度与 vEB 相当。我猜测常数因子会比 vEB 的幼稚实现要小一些，但这种说法只是基于直觉。

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

于 2017-07-11T08:55:13.960 回答
0

就提供 O(α(n)) 时间而言，它确实变得很棘手。这是我接近这个的想法：

  1. 既然我们知道了的范围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 范围内的所有值。type变量将被赋值，就好像true我们在树中插入的项目存在于集合 S 中一样。如果不存在，它将被标记为false。

这将花费 O(n) 时间来创建。可以及时删除O(logn)。O(logn)对于 pred(i)，如果我是正确的，我们可以实现平均案例时间复杂度。pred(i) 的算法应该是这样的：

  1. i在树中找到元素。如果 type 为真，则返回该元素的前序元素i的类型值（如果该前驱元素的类型值为 ）true。
  2. 如果是false，则重复该元素的下一个前任（即 i-1 的前任），直到我们找到一个元素 i type = true。
  3. 如果没有找到这样的前任type = true，则返回 0。

我希望我们可以进一步优化这种方法，使其在 pred(i) 的 O(α(n)) 中。

于 2017-07-11T08:58:28.050 回答