为什么红黑树删除功能的最坏情况旋转数是恒定的，但颜色翻转却不是？

Question

我在 Stack Overflow 上找到了这个 answer。答案意味着 在最坏的情况下，红黑树“删除”功能的旋转次数是恒定的，并且颜色翻转的数量与 Log(N) 成比例增长。 我还阅读了 脚本附在答案中。然而，我找不到任何证据证明这一说法。为什么这个说法是真的还是假的？可以用实际例子来证明吗？

Answer 1

可以用实际例子来证明吗？

一个例子永远不能作为有限旋转次数的证明。如果我们提供一个删除导致三次轮换的例子，这能证明什么？当然不是说这是单次删除的最大旋转次数。为此，您需要查看影响算法和旋转次数的所有可能性，并从中得出结论。

我将参考Wikipedia上描述的算法。简单案件和其他案件之间有区别。可能涉及旋转的情况，从删除black leaf（即有两个 NIL 子节点）开始（或转换为值交换）。

维基百科文章随后将此案例分为六个子类别：D1、D2、D3、D4、D5 和 D6。它提供了这个汇总表：

...我们有当前黑色 [N]ode 的 [P]arent、[S]ibling、[C]lose nephew 和 [D]istant nephew。

旋转

状态 D1 和 D4 是最终状态：不再发生旋转。

状态 D2 是一个过渡状态，可以转换为任何其他状态，甚至是“简单”情况（因此上表“下一步”列中的问号）

状态D3涉及旋转。然后它可能会过渡到 D4、D5 或 D6

状态 D5 涉及旋转并转换到状态 D6

状态D6涉及旋转，并结束该过程。

因此旋转仅发生在状态 D3、D5 和 D6 中。从上面可以清楚地看出，删除过程最多可以旋转3次。当我们从状态 D3 到达状态 D5，然后（总是）以状态 D6 结束时，就会发生这种情况。

着色

状态D2涉及着色，并且可能导致父级别的状态D2。所以这可以一直持续到根源。