6

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

要求：

  • key 是具有有限范围的整数1..N- 您可以为它分配一个数组（即内存不是问题）

操作：

  • insert(key, data)- O(1)
  • find(key)- O(1) - 返回带有数据的“节点”
  • delete(node)- O(1)
  • next(node)- O(1) - 找到下一个被占用的节点，按key给出的顺序
  • prev(node)- O(1)

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

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

4

1 回答 1

8

您可以使用Van Emde Boas 树来做到这一点。

树支持您需要的操作：

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 是密钥中的位数。

例如，如果您的所有键都是 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 位密钥。树的第一层将存储 2^8 (=256) 个子树的数组。第一个孩子负责从 0 到 255 的键，第二个负责键 256,257,..,511 等。

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

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

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

  1. 为每棵树存储一个最小值和最大值，因此需要 O(1) 来查看我们是否已达到我们的极限
  2. 辅助树用于存储非零子节点的索引。这棵辅助树是一棵 Van Emde Boas 树，其大小是原始大小的平方根。
于 2013-06-28T11:42:17.793 回答