c++ - std::map已知位置删除摊余的复杂度和红黑树重新着色的次数

Question

std::map::erase(iterator)的复杂度以O(1)摊销(例如，参见here)。尽管标准库没有规定实现方式，但事实上，这意味着将红黑树所需的重新平衡操作数摊销为O(1)。实际上，关于红黑树的Wikipedia条目seems to confirm this:

Restoring the red–black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion).

但似乎没有链接(我在其他地方找不到)。

由于转数是恒定的，因此摊销取决于节点根路径上所需的重新着色数量。尽管平衡树中的大多数节点都朝向树的底部(因此平均路径是对数的)，但显然它是摊销的O(1)，这令人惊讶且有趣。如何证明摊销的固定成本？

Answer 1

我将在此答案中假设您熟悉摊销分析，并且熟悉银行家的方法。我还要假设您知道红黑树不变式。

对于一些小的常数k，简短的答案是，将k个硬币放在每个没有一个红色 child 的黑色节点上。

请注意，红黑树中有多种不同的删除算法。用迭代器擦除显然需要自下而上的算法之一。此处的分析假设该算法的执行大致如下:

向上遍历，直到找到一个黑色节点。这总是可能的，因为根是黑色的，并且由于红色节点不能有红色的子节点，所以它的跳数绝不会超过两跳。

在O(1)时间内对根于该黑色节点的子树执行“修复”操作。如果修复程序降低了子树的高度或将根的颜色从黑色更改为红色，请向根再走一步，然后返回到＃1。

需要做一些工作才能看到＃2是可能的。实际上，这种复杂性是Sedgewick左倾红黑树的动机之一。这主要是枚举所有情况，进行一次或两次轮换，然后仔细检查您是否未违反任何不变性的问题。

fixup操作的一个变体(如果您已经有了另一个有效的变体，这很难找到)在遍历树的过程中保留了两个其他不变式:

当子树的高度减小1时，子树的根(a)最初有两个黑人 child (b)现在正好有一个红色 child 。

子树从不将颜色从黑色更改为红色。

因此，对于遍历的每个步骤，

子树的根有一个或两个红色子代。我们执行O(1)工作，最多添加O(1)个硬币，然后停止

我们执行O(1)工作，通过将具有两个黑色子节点的节点变成具有一个红色子节点的节点来获得O(1)硬币，并继续

案例2是 摊销后的免费，只要硬币数量足够大以支付案例2中的重组和重新着色费用。因此，删除的总摊销成本是我们在单个删除操作中达到案例＃1的次数，最多为一次，因为在我们执行删除操作后我们就停止了。

虽然这涵盖了解释算术的原理，但并没有真正解释为什么删除要摊销O(1)。

有时会教给学生有关摊销成本的一种情况是增加二进制数的情况。在最坏的情况下，成本为Ω(lg n)，但在摊销意义上，通过将恒定数量的硬币放在每个“1”数字上，成本为O(1)。

类似地，递减是通过将恒定数量的硬币放在每个“0”数字上来摊销O(1)。但是，即使在摊销设置中，将两者混合也会使每个成本Ω(lg n)，因为摊销分析取决于所有遍历步骤，除了最后一个步骤会返还恒定数量的硬币。

这个遍历是免费的，直到您停止为止，该主题类似于上面的红黑树分析。必须放置硬币的数字是代表将要进行的结构调整的数字。使用物理学家的方法，像这样将势能添加到每个数字的结构中。

考虑一个不同的二进制数字表示形式，其中的数字可以是0、1， 或2 (但是d_i仍然表示d_i * 2 ^ i)。这称为冗余二进制。现在，您可以将恒定数量的硬币放在所有0或2位数字上，并获得摊销的恒定时间增量和减量。原因是级联的递增或递减将0s或2s更改为1s，因此总是将硬币取回。

因此，使用两位数，递增或递减值将分摊O(1)，但不能同时摊销，而使用三位数，都可以摊销O(1)。

同样，插入或删除(但不能同时删除)在所有以下项中均摊销O(1):

黑色节点中只能有一个红色子节点的红黑树

AA树

2-3棵树

(a，2a-1)树，对于任何> 1的树

虽然插入和删除都在红黑树，(2,4)树和(a，2a)树中对于任何a> 1进行O(1)摊销。