Red-black 树 Java 中的空值 child

Question

对于Red-black二叉搜索树的Red-Black规则中的第四条规则（不确定它是否是我书中的第四条），从根到叶子的每条路径, or to a null child, must contain the same number of black nodes, null child 到底是什么？据我所知，它就像一个可以添加到节点的潜在 child 但实际上，它并不存在。

......................................................
                            25(black)                                                              
            20(black)                             50(red)                              
    --              --              --                 70(black)              
......................................................

书上说这个案例不符合 red-black 规则，我不知道为什么。我假设它与 null child 有关。因为看起来它满足所有的规则。根是黑色的，每个节点不是红色就是黑色，如果一个节点是红色的，它的 child 是黑色的。并且从根到叶子的每条路径都包含相同数量的黑色节点。那么 null child 究竟是如何使这种情况不遵循 red-black 规则的呢？

Answer 1

路径25, 50, --有1个黑色节点（25）；路径 25, 50, 70 有 2 个黑色节点（25 和 70）。通常，红黑树的规则不会区分叶子和空子节点；我们可以说 70 节点也有两个空子节点，它们是叶子。

Red-black 树 Java 中的空值 child

Null child in Red-black tree Java

java

red-black-tree