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

Question

我想实现具有与数组相关的操作的数据结构 - 即索引和链表 - 快速访问prev/next项.类似于稀疏数组,但内存不是问题 - 关注的是时间复杂性.

要求:

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

操作:

• insert(key, data) - O(1)
• find(key) - O(1) - 返回带有数据的"节点"
• delete(node) - O(1)
• next(node) - O(1) - 按密钥给出的顺序查找下一个占用节点
• prev(node) - O(1)

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

如果无法做到这一点,请提供证明.

Answer 1

你可以用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)
• Min O(1)

细节

这棵树的工作原理是使用大量的子树.

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

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

但是,这本身就会使查找下一个元素变得困难,因为我们可能需要搜索256个子树来查找非零元素.

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

1. 为每棵树存储最小值和最大值,因此O(1)工作是否已达到我们的极限
2. 辅助树用于存储非零孩子的索引.这个辅助树是Van Emde Boas树,其大小与原始大小的平方根相同.