std::map 已知位置擦除分摊复杂度和红黑树重新着色的次数
std::map Known-Position Erase Amortized Complexity And Number of Red-Black Tree Recolorings
std::map::erase(iterator) 的复杂性被分摊 O(1)（参见 here, for example). While the standard library does not dictate implementations, this de-facto means that the number of rebalancing operations needed for a red-black tree is amortized O(1). In fact, the Wikipedia entry on red-black trees 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).
但好像没有link（我在其他地方也找不到）。
由于旋转次数是恒定的，摊销是在节点根路径上需要重新着色的次数。虽然平衡树中的大多数节点都朝向树的底部（因此平均路径是对数的），但它显然被摊销了 O(1)，这是令人惊讶和有趣的。如何证明摊销不变成本？
在这个回答中，我假设您熟悉摊销分析并且熟悉银行家的方法。我还假设您知道 red-black 树不变量。
简短的回答是对于一些小的常量 k，将 k 个硬币放在没有恰好有一个红色的每个黑色节点上 child。
请注意，在 red-black 树中有许多不同的删除算法。使用迭代器擦除显然需要 bottom-up 算法之一。这里的分析假设算法执行大致如下：
向上遍历，直到找到黑色节点。这总是可能的，因为根是黑色的，而且它永远不会超过两跳，因为红色节点不能有红色 children.
对以该黑色节点为根的子树在 O(1) 时间内执行 "fixup" 操作。如果修复降低了子树的高度或将根的颜色从黑色更改为红色，则向根再移动一步并返回#1。
需要一些工作才能看到 #2 是可能的。事实上，这种复杂性正是 Sedgewick 的 left-leaning red-black 树的动机之一。这主要是枚举所有情况的问题，进行一次或两次旋转，然后仔细检查您是否没有违反任何不变量。
修复操作的一个变体（如果您已经有另一个有效变体，则不难找到）在向上遍历树的过程中保留了两个额外的不变量：
当子树的高度减1时，子树的根(a)原来有两个黑色children(b)现在正好有一个红色child.
子树的颜色永远不会从黑色变为红色。
因此，对于遍历的每一步，要么
子树的根有一两个红色children。我们执行 O(1) 的工作，最多添加 O(1) 个硬币，然后停止
我们执行 O(1) 的工作，通过将一个有两个黑色 children 的节点变成一个有一个红色的节点来取回 O(1) 个硬币 child，然后继续
案例 #2 免费摊销，只要硬币数量足够多以支付案例 #2 中重组和重新着色的成本。因此，删除的总摊销成本是我们在单个删除操作中命中案例 #1 的次数，最多为一次，因为命中后我们会停止。
虽然这涵盖了解释的算术机制，但它并没有真正解释为什么删除被分摊为 O(1)。
学生有时被教导摊余成本的案例之一是递增二进制数的情况。在最坏的情况下，成本是 Ω(lg n)，但在摊销意义上是 O(1)，通过在每个“1”数字上放置恒定数量的硬币。
类似地，递减是 O(1) 通过在每个“0”数字上放置恒定数量的硬币来摊销的。然而，混合这两者会使每个成本 Ω(lg n)，即使在摊销设置中也是如此，因为摊销分析取决于所有遍历步骤，除了最后一个返回恒定数量的硬币。
这个traversal-is-free-until-you-stop主题类似于上面的red-black树分析。硬币必须放在的数字是代表即将进行的结构调整的数字。使用物理学家的方法，像这样将势能添加到每个数字的结构中。
考虑二进制数的不同表示，其中数字可以是 0、1、 或 2（但数字 d_i 仍然代表 d_i * 2^i).这称为冗余二进制。现在，您可以在所有 0 或 2 位数字上放置固定数量的硬币，然后分摊 constant-time 增量和减量。原因是级联递增或递减将 0s 或 2s 更改为 1s，因此总能取回硬币。
因此，对于两位数，增量或减量是 O(1) 摊销的，但不是两者都摊销，而对于三位数，两者都可以摊销 O(1)。
类似地，插入或删除（但不是两者）在以下所有项中均摊为 O(1)：
Red-black 黑色节点只能有一个红色节点的树 child
AA-trees
2-3 棵树
(a,2a-1) 棵树，对于任何 a > 1。
虽然插入和删除都是 O(1) 分摊在 red-black 树、(2,4) 树和 (a,2a) 树中，对于任何 a > 1。
std::map::erase(iterator) 的复杂性被分摊 O(1)（参见 here, for example). While the standard library does not dictate implementations, this de-facto means that the number of rebalancing operations needed for a red-black tree is amortized O(1). In fact, the Wikipedia entry on red-black trees 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).
但好像没有link（我在其他地方也找不到）。
由于旋转次数是恒定的，摊销是在节点根路径上需要重新着色的次数。虽然平衡树中的大多数节点都朝向树的底部（因此平均路径是对数的），但它显然被摊销了 O(1)，这是令人惊讶和有趣的。如何证明摊销不变成本？
在这个回答中，我假设您熟悉摊销分析并且熟悉银行家的方法。我还假设您知道 red-black 树不变量。
简短的回答是对于一些小的常量 k，将 k 个硬币放在没有恰好有一个红色的每个黑色节点上 child。
请注意，在 red-black 树中有许多不同的删除算法。使用迭代器擦除显然需要 bottom-up 算法之一。这里的分析假设算法执行大致如下：
向上遍历，直到找到黑色节点。这总是可能的，因为根是黑色的，而且它永远不会超过两跳，因为红色节点不能有红色 children.
对以该黑色节点为根的子树在 O(1) 时间内执行 "fixup" 操作。如果修复降低了子树的高度或将根的颜色从黑色更改为红色，则向根再移动一步并返回#1。
需要一些工作才能看到 #2 是可能的。事实上，这种复杂性正是 Sedgewick 的 left-leaning red-black 树的动机之一。这主要是枚举所有情况的问题，进行一次或两次旋转，然后仔细检查您是否没有违反任何不变量。
修复操作的一个变体（如果您已经有另一个有效变体，则不难找到）在向上遍历树的过程中保留了两个额外的不变量：
当子树的高度减1时，子树的根(a)原来有两个黑色children(b)现在正好有一个红色child.
子树的颜色永远不会从黑色变为红色。
因此，对于遍历的每一步，要么
子树的根有一两个红色children。我们执行 O(1) 的工作，最多添加 O(1) 个硬币，然后停止
我们执行 O(1) 的工作，通过将一个有两个黑色 children 的节点变成一个有一个红色的节点来取回 O(1) 个硬币 child，然后继续
案例 #2 免费摊销，只要硬币数量足够多以支付案例 #2 中重组和重新着色的成本。因此，删除的总摊销成本是我们在单个删除操作中命中案例 #1 的次数，最多为一次，因为命中后我们会停止。
虽然这涵盖了解释的算术机制，但它并没有真正解释为什么删除被分摊为 O(1)。
学生有时被教导摊余成本的案例之一是递增二进制数的情况。在最坏的情况下，成本是 Ω(lg n)，但在摊销意义上是 O(1)，通过在每个“1”数字上放置恒定数量的硬币。
类似地，递减是 O(1) 通过在每个“0”数字上放置恒定数量的硬币来摊销的。然而，混合这两者会使每个成本 Ω(lg n)，即使在摊销设置中也是如此，因为摊销分析取决于所有遍历步骤，除了最后一个返回恒定数量的硬币。
这个traversal-is-free-until-you-stop主题类似于上面的red-black树分析。硬币必须放在的数字是代表即将进行的结构调整的数字。使用物理学家的方法，像这样将势能添加到每个数字的结构中。
考虑二进制数的不同表示，其中数字可以是 0、1、 或 2（但数字 d_i 仍然代表 d_i * 2^i).这称为冗余二进制。现在，您可以在所有 0 或 2 位数字上放置固定数量的硬币，然后分摊 constant-time 增量和减量。原因是级联递增或递减将 0s 或 2s 更改为 1s，因此总能取回硬币。
因此，对于两位数，增量或减量是 O(1) 摊销的，但不是两者都摊销，而对于三位数，两者都可以摊销 O(1)。
类似地，插入或删除（但不是两者）在以下所有项中均摊为 O(1)：
Red-black 黑色节点只能有一个红色节点的树 child
AA-trees
2-3 棵树
(a,2a-1) 棵树，对于任何 a > 1。
虽然插入和删除都是 O(1) 分摊在 red-black 树、(2,4) 树和 (a,2a) 树中，对于任何 a > 1。