algorithm - 具有 O(1) 索引和 O(1) prev 和 next 的稀疏数组

Question

我想通过与数组相关的操作来实现数据结构 - 即索引和链表 - 快速访问上一个/下一个项目。类似于稀疏数组，但内存不是问题 - 问题是时间复杂度。

要求:

• key 是整数，范围有限 1..N - 你可以为它分配一个数组(即内存不是问题)

操作:

• 插入(键，数据) - O(1)
• find(key) - O(1) - 返回包含数据的“节点”
• 删除(节点) - O(1)
• next(node) - O(1) - 按照 key 给出的顺序查找下一个占用的节点
• prev(node) - O(1)

我正在考虑在一个数组中实现，指针指向下一个/上一个占用的项目，但我在 insert 操作中遇到问题 - 我如何找到上一个和下一个项目，即位置在双链表中放置新项目的位置 - 我不知道如何制作这个 O(1)。

如果这不可能，请提供证明。

Answer 1

您可以使用 Van Emde Boas tree 来做到这一点.

树支持你需要的操作:

Insert: insert a key/value pair with an m-bit key
Delete: remove the key/value pair with a given key
Lookup: find the value associated with a given key
FindNext: find the key/value pair with the smallest key at least a given k
FindPrevious: find the key/value pair with the largest key at most a given k

时间复杂度为 O(logm)，其中 m 是 key 中的位数。

例如，如果您的所有 key 都是 0 到 65535 之间的 16 位整数，则 m 将为 16。

编辑

如果键在 1..N 范围内，则每个操作的复杂度为 O(loglogN)。

该树还支持最小和最大操作，其复杂度为 O(1)。

• 插入 O(loglogN)
• 找到 O(loglogN)
• 删除O(loglogN)
• 下一个 O(loglogN)
• 上一个 O(loglogN)
• 最大 O(1)
• 最小 O(1)

详情

这棵树通过使用大量子树来工作。

例如，假设我们有 16 位 key 。树的第一层将存储 2^8 (=256) 个子树的数组。第一个 child 负责从 0 到 255 的键，第二个 child 负责键 256,257,..,511 等。

这使得查找节点是否存在变得非常容易，因为我们可以直接转到相应的数组元素。

但是，这本身会使找到下一个元素变得困难，因为我们可能需要搜索 256 个子树才能找到非零元素。

Van Emde Boas 树包含两个附加项，可以轻松找到下一个元素:

1. 为每棵树存储了最小值和最大值，因此 O(1) 的工作量可以确定我们是否已达到限制
2. 辅助树用于存储非零子节点的索引。这棵辅助树是 Van Emde Boas 树，其大小是原始大小的平方根。