红黑树在所有路径上具有相同数量的黑色节点意味着什么？
What does it mean for a red black tree to have same number of black nodes on all paths?
我不明白这个条件是什么意思：“对于每个节点，从该节点到后代叶子的所有路径都包含相同数量的黑色节点”
让我们举个例子树：
声明说“对于每个节点...”，所以让我们选择一个这样的节点作为示例，根，节点 13。
说的是“后代叶子”。这些叶子是值为 6、11、15、22 和 27 的节点。它们是我们选择的节点 13 的后代，它们是叶子，所以 “后代叶子”.
"从节点到后代叶子的所有路径"因此是以下路径：
- 13→8→1→6
- 13→8→11
- 13→17→15
- 13→17→25→22
- 13→17→25→27
现在计算每条路径上的黑色节点：
- 13→8→1→6有2个黑色节点（13和1）
- 13→8→11有2个黑色节点（13和11）
- 13→17→15有2个黑色节点（13和15）
- 13→17→25→22有2个黑色节点（13和25）
- 13→17→25→27有2个黑色节点（13和25）
确实如此，我们看到 “从节点到后代叶子的所有路径都包含相同数量的黑色节点”：对于我们的示例树和选定节点，正好是 2 个。
您可以对另一个节点重复此练习，例如节点 8。然后 “后代叶子” 仅是节点 6 和 11。
现在的结果是：
- 8→1→6有1个黑色节点(1)
- 8→11有1个黑色节点(11)
再一次，声明是正确的。实际上，当该语句对根为真时，对所有节点都为真。
我不明白这个条件是什么意思：“对于每个节点，从该节点到后代叶子的所有路径都包含相同数量的黑色节点”
让我们举个例子树：
声明说“对于每个节点...”，所以让我们选择一个这样的节点作为示例，根，节点 13。
说的是“后代叶子”。这些叶子是值为 6、11、15、22 和 27 的节点。它们是我们选择的节点 13 的后代，它们是叶子，所以 “后代叶子”.
"从节点到后代叶子的所有路径"因此是以下路径：
- 13→8→1→6
- 13→8→11
- 13→17→15
- 13→17→25→22
- 13→17→25→27
现在计算每条路径上的黑色节点：
- 13→8→1→6有2个黑色节点（13和1）
- 13→8→11有2个黑色节点（13和11）
- 13→17→15有2个黑色节点（13和15）
- 13→17→25→22有2个黑色节点（13和25）
- 13→17→25→27有2个黑色节点（13和25）
确实如此，我们看到 “从节点到后代叶子的所有路径都包含相同数量的黑色节点”：对于我们的示例树和选定节点，正好是 2 个。
您可以对另一个节点重复此练习，例如节点 8。然后 “后代叶子” 仅是节点 6 和 11。
现在的结果是：
- 8→1→6有1个黑色节点(1)
- 8→11有1个黑色节点(11)
再一次，声明是正确的。实际上，当该语句对根为真时，对所有节点都为真。