performance - 有没有什么方法可以根据插入/删除的顺序有效地重建集合？

Question

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

假设我有一系列操作，而不是实际的集合(例如 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 —两个 O(N) 操作 — 对于每个元素。

---

更新:假设操作的“序列”实际上是一个具体的集合，其计数是已知的并且可以通过索引随机访问(因此，例如 ListOperation<T>[] )。我们还假设 结果 集合的实际计数是已知的(但实际上，通过计算插入和删除的次数，在 O(N) 中算出这将是微不足道的)。还有其他想法吗？

Answer 1

我认为您可以在 O(n lg n) 中通过使用索引平衡二叉树(一种二叉树，其中每个节点存储其左右节点的数量)来完成此操作。使用这种结构，您可以通过遍历树找到新元素所属的位置，然后进行任何必要的修正以维持平衡条件(例如，如果它是一棵红黑树，你会做一个红黑树修复)。

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

我将对此进行更多考虑，看看我是否可以想出一种在线性时间内完成此操作的方法。同时，这至少表明可以在次二次时间内做到这一点。