algorithm - 4 节点红黑树应该是什么样子

Question

嗨，我以前对红黑树知之甚少，也许这是一个愚蠢的问题。
这是一个 4 节点树：

它是合法的红黑树吗？在我看来，它实际上违反了红黑树的规则：

3. 每个红色节点的两个子节点都涂成黑色。
4. 从根到树叶的每条路径都包含相同数量（“黑色高度”）的黑色节点。

如果不是，4 节点红黑应该是什么样子？
谢谢

Answer 1

您是正确的，这棵树违反了红黑树的规则，因为路径 3-2-1-Null 穿过 3 个黑色节点，而 3-4-Null 只穿过 2 个。

回想一下，没有限制黑色节点必须将其子节点涂成红色，只有相反。即使一棵具有所有黑色节点的树在技术上也是一棵红黑树，只要它是平衡的并因此满足“从根到树叶的每条路径都包含相同数量（'黑色高度'）的黑色节点。”

因此，您可以通过将节点 2 和 4 涂成黑色并将节点 1 涂成红色来使这棵树成为有效的红黑树。请注意节点 1（唯一的红色节点）仍然有 2 个黑色子节点，并且从根到叶的所有路径都将命中 3 个黑色节点。因此满足红黑树的规则。