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

Question

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

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

Answer 1

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

想象一棵树，如下所示：

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

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

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

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