您可以使用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 树包含两个添加项,可以轻松找到下一个元素:
- 为每棵树存储一个最小值和最大值,因此需要 O(1) 来查看我们是否已达到我们的极限
- 辅助树用于存储非零子节点的索引。这棵辅助树是一棵 Van Emde Boas 树,其大小是原始大小的平方根。