红黑树 - 黑色高度限制

Question

我正在读关于红黑树的维基.

有人可以详细说明第5条限制:

1. 节点为红色或黑色.

2. 根是黑色的.

3. 所有叶子(NIL)都是黑色的.(所有叶子的颜色与根相同.)

4. 每个红色节点的两个孩子都是黑色的.

5. 从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色节点.

我在理解它时遇到了困难,因为在最后一个插入案例(wiki上的案例5)给出了示例RBT的状态后,我们得到了:

4和5是否有比1,2和3更多的黑色节点？

Answer 1

1,2,3,4和5都是子树.我们知道树1,2和3中根节点的颜色是黑色.我们不知道节点1-5中的任何节点是否是叶节点,因为这种插入的情况可能已经在一些N上递归地调用,该N是新插入的节点的祖父(来自插入情况3).

在旋转之前和之后,子树1,2和3都低于一个黑色节点(G之前,P之后),并且子树4和5低于两个黑色节点(之前是G和U,之后是P和U).子树1,2和3每个都有一个黑色节点而不是子树4和5.