证明红黑树在将一组 S 的红色节点变为黑色后仍然有效

Question

我目前正在为以下问题绞尽脑汁：证明，在一棵红黑树T中，如果从根到叶子的每条路径都包含至少有一个红色节点，那么我们可以 select T 中的一组红色节点来着色黑色，这样 T 仍然是一个有效的红黑树，并且黑色高度增加 1。

任何人都有关于如何解决这个问题的任何提示，我什至迷路了

Answer 1

想到它的简单方法是将红色节点推到树上，然后再次将根变黑。

想象一棵如下所示的树：

       B
  R        B
 B   B  R  B
B B B B B B R R

如果每条路径上都有一个红色节点，那么至少会有一个黑色节点和两个红色子节点。如果在发生这种情况的每个位置都将红色节点向上推到树上，从底部开始最终会将红色节点推到树根，此时您可以翻转颜色并且树高增加了一个。

此外，如果您达到了整个级别为红色的配置，则可以在不改变树属性的情况下翻转该级别的所有节点，并且高度再次增加一倍。

如果某些路径有多个红色节点，则有点棘手，在这种情况下，您需要从该路径中最顶层的红色节点开始工作，并从另一个分支推送一个红色节点以匹配它。

Prove that a red-black tree remains valid after turning a set S of red nodes black