java - 红黑树-黑色高度限制

Question

我正在阅读有关 Red-Black Trees 的维基百科.

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

1. A node is either red or black.

2. The root is black.

3. All leaves (NIL) are black. (All leaves are same color as the root.)

4. Both children of every red node are black.

5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

自从给出示例 RBT 在 the final case of insertion 之后的状态后，我很难理解它(wiki 上的案例 5)给我们:

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多一个黑色节点。