algorithm - 具有高效查找缺失的一组键的数据结构

Question

我正在寻找一个支持以下操作的数据结构整数键 k，范围从 0 到 M-1。

• O(1) 或 O(log n) insert(k), erase(k), lookup(k).
• O(1) 或 O(log n) 的特殊操作 find_missing_key() 返回结构中当前不存在的任何键。
• O(n) 或 O(n log n) 空间。尤其。不应该是 O(M)。

一个明显的实现是一个“自由键列表”结构，实现为一个堆；但这需要 O(M) 空间。是否有某种数据结构可以满足所有要求？

Answer 1

使用二叉线段树。

树中的每个节点代表一个范围内的整数[a,b]，并且要么是叶子[a,a]，要么分成代表范围[a,m]和[m+1,b]的两个节点其中 m 是 (a+b)/2。

仅在必要时扩展节点，因此最初我们只有一个范围为 [0,M-1](或 [0,M)，如果您愿意)的根节点

在每个节点中，记录该子树中有多少已用/空闲点。

x 的插入、查找和删除是 O(log n):继续分割直到到达 [x,x]，并更新从该节点到根的路径上的所有内容。

find_missing_key 也是 O(log n):由于您知道每个段的大小以及其中有多少空闲元素，因此您可以在每个节点决定是向左还是向右以找到空闲元素。

(编辑:顺便说一下，这还允许您找到第一个、最后一个甚至第 i_th 个免费元素，无需额外费用。)