的复杂性std::map::erase(iterator)摊销为O(1)（例如，请参见此处）。虽然标准库没有规定实现，但事实上这意味着红黑树所需的重新平衡操作的数量是摊销的O(1)。事实上，关于红黑树的维基百科条目似乎证实了这一点：
恢复红黑属性需要少量（O(log n) 或摊销的 O(1)）颜色变化（在实践中非常快）并且不超过三个树旋转（两个用于插入）。
但似乎没有链接（我在其他地方找不到它）。
由于旋转次数是恒定的，因此摊销取决于节点根路径上所需的重新着色次数。虽然平衡树中的大多数节点都朝向树的底部（因此平均路径是对数的），但它显然是摊销的O(1)，这是令人惊讶和有趣的。如何证明摊余不变成本？
在这个答案中，我假设您熟悉摊销分析并且对银行家的方法感到满意。我还假设您知道红黑树不变量。
简短的回答是对于一些小的常数 k，将 k 个硬币放在每个没有恰好一个红色孩子的黑色节点上。
请注意，在红黑树中有许多不同的删除算法。使用迭代器擦除显然需要一种自下而上的算法。这里的分析假设算法大致执行如下：
向上遍历，直到找到一个黑色节点。这总是可能的，因为根是黑色的，而且它永远不会超过两跳，因为红色节点不能有红色的孩子。
在以该黑色节点为根的子树上在 O(1) 时间内执行“修复”操作。如果修复降低了子树的高度或将根的颜色从黑色更改为红色，则向根再走一步并返回#1。
需要一些工作才能看到 #2 是可能的。事实上，这种复杂性是 Sedgewick 左倾红黑树的动机之一。这主要是枚举所有情况的问题，进行单轮或双轮旋转，然后仔细检查您没有违反任何不变量。
fixup 操作的一个变体（如果您已经有另一个有效变体，不难找到）在向上遍历树的过程中保留了两个额外的不变量：
当子树的高度减少 1 时，子树的根 (a) 原来有两个黑色孩子 (b) 现在正好有一个红色孩子。
子树永远不会将颜色从黑色变为红色。
因此，对于遍历的每一步，要么
子树的根有一个或两个红色的孩子。我们执行 O(1) 工作，最多添加 O(1) 个硬币，然后停止
我们执行 O(1) 工作，通过将具有两个黑色孩子的节点变成具有一个红色孩子的节点来取回 O(1) 硬币，然后继续
案例#2 是免费摊销的，只要硬币的数量足以支付案例#2 的重组和重新着色成本。因此，删除的总摊销成本是我们在单个删除操作中击中 case #1 的次数，最多为一次，因为在击中它之后我们会停止。
虽然这涵盖了解释的算术机制，但它并没有真正解释为什么delete 摊销 O(1)。
有时向学生讲授摊销成本的案例之一是递增二进制数的案例。在最坏的情况下，成本是 Ω(lg n)，但在摊销的意义上，成本是 O(1)，通过在每个“1”位上放置恒定数量的硬币。
类似地，通过在每个“0”位上放置恒定数量的硬币，递减是 O(1) 摊销。然而，将两者混合会使每个成本 Ω(lg n)，即使在摊销设置中，因为摊销分析取决于所有遍历步骤，除了最后一个返回恒定数量的硬币。
这个 traversal-is-free-until-you-stop 主题类似于上面的红黑树分析。硬币必须放在的数字是代表即将进行的结构调整的数字。使用物理学家的方法，像这样将势能添加到每个数字的结构中。
考虑二进制数的不同表示形式，其中数字可以是 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) 树，对于任何 a > 1。
虽然对于任何 a > 1，插入和删除都是 O(1) 在红黑树、(2,4) 树和 (a,2a) 树中摊销的。