std::map::erase(iterator)的复杂性被摊销O（1）（例如，请参阅此处）。虽然标准库没有规定实现，但这实际上意味着红黑树所需的再平衡操作数量摊销 O（1）。事实上，维基百科关于红黑树的条目似乎证实了这一点：
恢复红黑属性需要少量（O（log n）或摊销O（1））的颜色变化（在实践中非常快）和不超过三次树旋转（两次用于插入）。
但似乎没有链接（我在其他地方找不到它）。
由于旋转次数是恒定的，因此摊销取决于节点根路径上所需的重新着色次数。虽然平衡树中的大多数节点都朝向树的底部（因此平均路径是对数的），但它显然是摊销的 O（1），这令人惊讶和有趣。如何证明摊销固定成本？
我在这个答案中假设你熟悉摊销分析，并且对银行家的方法感到满意。我还假设你知道红黑树不变量。
简短的回答是对于一些小常数k，将k个硬币放在每个没有一个红色子节点的黑色节点上。
请注意，在红黑树中有许多不同的删除算法。使用迭代器擦除显然需要一种自下而上的算法。 此处的分析假设该算法大致执行如下：
-
向上移动，直到找到黑色节点。这始终是可能的，因为根是黑色的，并且它永远不会超过两个跃点，因为红色节点不能有红色子节点。
-
在 O（1） 时间内对根植于该黑色节点的子树执行"修正"操作。如果修正降低了子树的高度或将根的颜色从黑色更改为红色，请向根再遍历一步并返回到 #1。
需要一些工作才能看到#2是可能的。事实上，这种复杂性是塞奇威克左倾红黑树的动机之一。这主要是枚举所有情况的问题，进行单次或两次旋转，然后仔细检查您没有违反任何不变量。
修正操作的一个变体（如果您已经有另一个有效的变体，则不难找到）在遍历树的过程中保留了两个额外的不变量：
- 当子树
的高度降低 1 时，子树 （a） 的根最初有两个黑人孩子 （b） 现在正好有一个红色孩子。
子树永远不会将颜色从黑色更改为红色。
因此，对于遍历的每个步骤，要么
- 子树
的根有一个或两个红色子树。我们执行 O（1） 工作，最多添加 O（1） 个硬币，然后停止
我们执行 O（1） 工作，通过将具有两个黑人子节点的节点转换为具有一个红色子节点来取回 O（1） 硬币，然后继续
#2 是免费摊销的，只要硬币的数量足够大以支付案例 #2 中的重组和重新着色成本。因此，删除的总摊销成本是我们在单个删除操作中遇到案例 #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）：
黑树，其中黑色节点只能有一个红色子节点
AA树
2-3棵树
（a，2a-1） 树，对于任何 a> 1.
虽然插入和删除都是 O（1） 摊销在红黑树、（2,4） 树和 （a，2a） 树中，对于任何 a> 1。