jca*_*cai 4 algorithm data-structures
我正在寻找一种数据结构,支持k从0到M-1的整数键的以下操作.
insert(k),erase(k),lookup(k).find_missing_key()返回结构中当前不存在的任何键的特殊操作.一个明显的实现是一个"list-of-free-keys"结构,实现为堆; 但这需要O(M)空间.是否有一些数据结构满足所有要求？
使用二进制段树.
树中的每个节点表示一个整数范围[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个自由元素,无需额外费用.)