问查找具有O(1)索引和O(log(n))插入和删除的数据容器

EN

首先，我想指出，如果k真的是一个随机数，那么可能值得考虑的是，这个问题可能是完全不同的:要求k-最小元素，在可用元素的范围内，k是随机的，基本上是……随机挑选一个元素。而且可以做很多不同的事情。

这里我假设您实际上需要选择一些特定的，如果是任意的，k。

考虑到强的前提条件是按顺序插入元素，有一个简单的解决方案：

• 由于您的元素是按顺序给出的，所以只需将它们一个接一个地添加到数组中；也就是说，您有一些(无限)表T，以及光标c，最初是c := 1，在添加元素时，做Tc := x和c := c+1。
• 当您想要访问k个最小的元素时，只需看看Tk。

当然，问题是在删除元素时，会在表中创建空白，这样Tk元素可能不是k最小的，而是j-最小的j <= k，因为k之前的一些单元格是空的。

这样就足以跟踪您删除的元素，知道删除了多少小于k的，您如何在最多的时间内做到这一点？通过使用范围树或类似类型的数据结构。范围树是一种结构，允许您为X到Y之间的所有整数添加整数，然后对所有整数进行查询。因此，每当您删除一个项目时，只需将它添加到范围树中；当您查找k-最小元素时，对删除的所有整数进行查询；假设增量已被删除，那么第k个元素将位于Tk+delta中。

有两个小渔获量，需要进行一些修正：

• range树返回时间范围O(log n)，但是要计数范围中的元素数，必须遍历范围中的每个元素，因此这会增加一个时间O(D)，其中D是范围内已删除项的数目；要消除这个问题，必须修改范围树结构，以便在每个节点跟踪子树中不同元素的数量。保持这个计数只需花费O(log )，这不会影响整个复杂性，而且这是一个相当微不足道的修改。
• 事实上，只进行一个查询是行不通的。实际上，如果在范围1到k中删除了增量元素，那么需要确保range k+1到k+delta中没有删除元素，依此类推。完整的算法将是沿着下面的路线。

KthSmallest(T,k) := {
  a = 1;  b = k;  delta

  do {
    delta = deletedInRange(a, b)
    a = b + 1
    b = b + delta
  while( delta > 0 )

  return T[b]
}

此操作的确切复杂性取决于您如何准确地进行删除，但是如果您的元素被随机地一致删除，那么迭代的次数应该相当少。

有一个树 (带有源代码的)，对于所有三个操作(insert、delete、index)都是O(lg n)。

实际上，这个数据结构的可接受名称似乎是"顺序统计树“。(除了索引之外，它还被定义为支持O(lg N)中的索引(元素)。)

顺便说一句，与O(lg n)相比，O(1)并不是很大的优势。这种差异往往被实践中的常量因素所压倒。(数据结构中有1e18项吗？)如果我们把它设为上界，那就等于60左右的常数因子。)

调查堆。插入和删除应该是O(log )，最小元素的窥视是O(1)。然而，对K‘’th元素的窥视或检索将再次是O(log )。

编辑:正如amit所说，检索比偷看要昂贵得多。