std :: map已知位置擦除摊销的复杂性和红黑树重新着色的数量

Question

std::map::erase(iterator)摊销的复杂性为O(1)(例如,见这里).虽然标准库没有规定实现,但事实上这意味着红黑树所需的重新平衡操作的数量是摊销的O(1).事实上,关于红黑树的维基百科条目似乎证实了这一点:

恢复红黑属性需要少量(O(log n)或摊销的O(1))颜色变化(实际上非常快)和不超过三次树旋转(两次插入).

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

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

Answer 1

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

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

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

需要做一些工作才能看到#2 是可能的。事实上，这种复杂性正是塞奇威克左倾红黑树的动机之一。这主要是一个枚举所有情况的问题，进行一次或两次旋转，然后仔细检查是否违反了任何不变量。

修复操作的一个变体（如果您已经有另一个有效变体，则不难找到）在遍历树的过程中保留了两个额外的不变量：

因此，对于遍历的每一步，要么

案例#2 是免费摊销的，只要代币数量足够大，足以支付案例#2 中的重组和重新着色的成本。因此，删除的总摊销成本是我们在单个删除操作中遇到情况 #1 的次数，最多为 1 次，因为遇到它后我们就会停止。

虽然这涵盖了解释的算术机制，但它并没有真正解释为什么删除的摊销时间为 O(1)。

有时向学生教授有关摊余成本的案例之一是递增二进制数的情况。在最坏的情况下，成本为 Ω(lg n)，但在摊销意义上为 O(1)，即在每个“1”数字上放置恒定数量的硬币。

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

这种遍历自由直至停止的主题与上面的红黑树分析类似。硬币必须放的数字是代表即将进行结构性调整的数字。使用物理学家的方法，势能被添加到每个数字的结构中，如下所示。

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

因此，对于两位数，递增或递减的摊销时间为 O(1)，但不能同时摊销，而对于三位数，两者都可以摊销 O(1)。

类似地，插入或删除（但不是两者）均摊销为 O(1)：

对于任何 a > 1，插入和删除在红黑树、(2,4) 树和 (a,2a) 树中均摊为 O(1)。