algorithm - 删除 O(log N) 中小于 k 的元素的数据结构，其中 N 是元素数

Question

下面函数都在O(log N)中的数据结构应该如何实现？

insert(x) - 添加整数到集合

member(x) - 检查集合是否包含整数 x

delete(x) - 从集合中删除整数 x

删除小于(x)删除所有等于或小于k的数

我唯一能想到的是使用某种平衡的 BST 来获得插入、成员和删除的 O(log N)。

deleteLessThan() 函数将类似于:找到大于 k 的最小元素，删除其左子树，然后重新平衡。但是，如果删除其中一个子树，是否可以在 O(log N) 中重新平衡 BST？

Answer 1

摊销的 log N 是否足够好？在这种情况下，您可以使用拉伸(stretch)树。除了删除元素 <= k 之外的所有操作都与维基百科上的解释相同。余下操作将大于k的最小元素展开到最顶层，删除其左子树。

如果您允许摊销，您可以轻松地考虑在 O(M) 时间内从 N 个节点中删除 M 个节点。