红黑树的性质
Properties of Red-Black Tree
红黑树的属性：
- 每个节点不是红色就是黑色。
- 根是黑色的
- 每一片叶子 (NIL) 都是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的。
- 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点。
根据属性，这些红黑树是有效的还是无效的？
一个。
我认为这是有效的
乙。
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
摄氏度。
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
D.
我认为这是无效的，因为它违反了 属性 4?
我理解 RBtree 的这些属性了吗？如果不是，我哪里错了？
您已正确列出 Red-Black 棵树的属性。在这四棵树中，只有 C 不是有效的 red-black 树：
这是一棵有效的树。 Wikipedia 确认：
every perfect binary tree that consists only of black nodes is a red–black tree.
I think this is valid, but I am not sure since there two adjacent red nodes?
有效。红色节点是兄弟节点是没有问题的。他们只是不应该处于 parent-child 关系中。
I think this is valid, but I am not sure since there two adjacent red nodes?
无效。不是因为相邻的红色节点，而是因为 属性 5. 标签为 12 的节点有通往其叶子的路径，该叶子具有不同数量的黑色节点。节点 25 相同。
作为一般规则，红色节点永远不会恰好有一个 NIL-leaf 作为 child。它的 children 要么都是 NIL-leaves，要么都是（黑色）内部节点。这是从属性得出的。
I think this is not valid since it violate Property 4?
属性4没有违反：红色节点的children是NIL叶子（这里没有可视化），是黑色的。这些红色节点具有黑色 NIL 叶子作为兄弟姐妹的事实是无关紧要的：没有关于兄弟姐妹的规则。所以这是有效的。
有关结合树 C 和 D 特征的示例，请参阅 Wikipedia article 中描述的这棵有效树，它还描述了 NIL 叶子：
A、B 和 D 是有效的 red-black 树
C 无效 red-black 树，因为从根到叶的黑色高度不一样。它在某些路径中为 2，在其他路径中为 1。它违反了您所说的规则 5。
如果 12 的右边 child 是黑色的，25 的左边 child 是黑色的，那么它将是一棵 red-black 树。
红黑树基本上等同于2-3-4树（4-Btree），尽管splitting/swapping方法是颠倒的。
2-3-4 树有固定大小的 3 节点桶。黑色表示它是 3-bucket 的中心节点。任何红黑树都被视为具有空节点（黑洞和红洞）的完美 quadtree/binary 树（3 节点桶）。
换句话说，每个黑色节点（每个3-bucket）在完美树中都有其绝对位置（2维唯一笛卡尔或4-adic/2-adic唯一分数）。
NIL 节点只是要保存的额外标志space；您没有足够的内存来存储完美的 quadtree/binary 树。
检查红黑树最简单的方法是检查每个黑色节点是否是一个新的桶（向下）并且每个红色节点都与上面的黑色节点（同一个桶）分组。如果中央黑色节点的红色节点少于2个，则只需在中央黑色节点（左右）旁边添加空的红色孔即可。
新的黑节点永远是上一个黑节点的孙节点，每个黑节点只能有两个红色子节点，不能有黑色子节点。如果红色女儿（母亲）为空（dead/unborn），则无母亲的孙子节点直接链接到其祖父节点。
一个没娘的黑孙子节点没有兄弟，但他身边可以有一个黑表哥节点；这两个堂兄弟与同一个祖父有关。
四叉树是二叉树的子集。
所有黑色节点的高度都是偶数(2,4,6...)，所有红色节点的高度都是奇数(1,3,5...)。或者，您可以使用半单位 0.5。
3-bucket 的大小固定为 3；只需添加额外的红色孔（未出生的未链接的红色女儿）即可制成 3 号。
红黑树的属性：
- 每个节点不是红色就是黑色。
- 根是黑色的
- 每一片叶子 (NIL) 都是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的。
- 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点。
根据属性，这些红黑树是有效的还是无效的？
一个。
我认为这是有效的
乙。
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
摄氏度。
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
D.
我认为这是无效的，因为它违反了 属性 4?
我理解 RBtree 的这些属性了吗？如果不是，我哪里错了？
您已正确列出 Red-Black 棵树的属性。在这四棵树中，只有 C 不是有效的 red-black 树：
这是一棵有效的树。 Wikipedia 确认：
every perfect binary tree that consists only of black nodes is a red–black tree.
I think this is valid, but I am not sure since there two adjacent red nodes?
有效。红色节点是兄弟节点是没有问题的。他们只是不应该处于 parent-child 关系中。
I think this is valid, but I am not sure since there two adjacent red nodes?
无效。不是因为相邻的红色节点，而是因为 属性 5. 标签为 12 的节点有通往其叶子的路径，该叶子具有不同数量的黑色节点。节点 25 相同。
作为一般规则，红色节点永远不会恰好有一个 NIL-leaf 作为 child。它的 children 要么都是 NIL-leaves，要么都是（黑色）内部节点。这是从属性得出的。
I think this is not valid since it violate Property 4?
属性4没有违反：红色节点的children是NIL叶子（这里没有可视化），是黑色的。这些红色节点具有黑色 NIL 叶子作为兄弟姐妹的事实是无关紧要的：没有关于兄弟姐妹的规则。所以这是有效的。
有关结合树 C 和 D 特征的示例，请参阅 Wikipedia article 中描述的这棵有效树，它还描述了 NIL 叶子：
A、B 和 D 是有效的 red-black 树
C 无效 red-black 树，因为从根到叶的黑色高度不一样。它在某些路径中为 2，在其他路径中为 1。它违反了您所说的规则 5。
如果 12 的右边 child 是黑色的，25 的左边 child 是黑色的，那么它将是一棵 red-black 树。
红黑树基本上等同于2-3-4树（4-Btree），尽管splitting/swapping方法是颠倒的。 2-3-4 树有固定大小的 3 节点桶。黑色表示它是 3-bucket 的中心节点。任何红黑树都被视为具有空节点（黑洞和红洞）的完美 quadtree/binary 树（3 节点桶）。
换句话说，每个黑色节点（每个3-bucket）在完美树中都有其绝对位置（2维唯一笛卡尔或4-adic/2-adic唯一分数）。
NIL 节点只是要保存的额外标志space；您没有足够的内存来存储完美的 quadtree/binary 树。
检查红黑树最简单的方法是检查每个黑色节点是否是一个新的桶（向下）并且每个红色节点都与上面的黑色节点（同一个桶）分组。如果中央黑色节点的红色节点少于2个，则只需在中央黑色节点（左右）旁边添加空的红色孔即可。
新的黑节点永远是上一个黑节点的孙节点，每个黑节点只能有两个红色子节点，不能有黑色子节点。如果红色女儿（母亲）为空（dead/unborn），则无母亲的孙子节点直接链接到其祖父节点。
一个没娘的黑孙子节点没有兄弟，但他身边可以有一个黑表哥节点；这两个堂兄弟与同一个祖父有关。
四叉树是二叉树的子集。
所有黑色节点的高度都是偶数(2,4,6...)，所有红色节点的高度都是奇数(1,3,5...)。或者，您可以使用半单位 0.5。
3-bucket 的大小固定为 3；只需添加额外的红色孔（未出生的未链接的红色女儿）即可制成 3 号。