有没有办法根据一系列插入/删除有效地重建集合？

Question

注意:下面的代码恰好是C#,但实际上任何语言的答案对我都有帮助.

假设不是实际的集合(例如,a List<T>),我有一系列操作,每个操作看起来像这样:

struct ListOperation<T>
{
    public enum OperationType { Insert, Remove }

    public OperationType Type;
    public T Element; // irrelevant for OperationType.Remove
    public int Index;
}

是否有某种方法可以根据一系列此类操作有效地 "重建"集合？

特别是,我希望避免显而易见(低效)的实现,基本上只为每个元素创建一个List<T>和调用Insert以及RemoveAt-both O(N)操作.

---

更新:假设操作的"序列"实际上是一个具体的集合,其计数是已知的,并且可以通过索引随机访问(ListOperation<T>[]例如,像a ).我们还要说结果集合的实际计数是已知的(但实际上,无论如何,通过计算插入和删除来计算O(N)是微不足道的).还有其他想法吗？

Answer 1

我认为你可以通过使用索引平衡二叉树(二进制树,其中每个节点存储左右节点的数量)在O(n lg n)中执行此操作.使用这种结构,您可以通过遍历树来查找新元素所属的位置,从而在任何点获得最坏情况的O(lg n)插入或删除,然后执行任何必要的修复以维持平衡条件(例如如果它是一棵红黑树,你会做一个红黑树修复.

给定此设置,您可以在O(n lg n)中将所有操作重放到这样的树结构中,因为每个单独的操作最多需要O(lg n)才能完成.一旦你有了树,你就可以对元素进行顺序遍历,使它们以正确的顺序返回,并且可以在O(n)时间内将所有值附加到结果列表中,以获得O(n lg) N).

我将更多地考虑这一点,看看我是否能够在线性时间内想出这样做的方法.与此同时,这至少表明在次级时间内可以做到这一点.