红黑树的性质:
- 每个节点要么是红色要么是黑色。
- 根是黑色的。
- 每片叶子 (NIL) 都是黑色的。
- 如果一个节点是红色的，那么它的两个 child 都是黑色的。
- 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点。
根据属性，这些红黑树是有效的还是无效的？
一个。 
我认为这是有效的
B. 
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
C. 
我认为这是有效的，但我不确定，因为有两个相邻的红色节点？
D. 
我认为这是无效的，因为它违反了属性 4？
我是否理解 RBtree 的这些属性？如果不是，我哪里错了？
最佳答案
您已正确列出红黑树的属性。四棵树中只有 C 不是有效的红黑树:
A.
这是一棵有效的树。 Wikipedia确认:
every perfect binary tree that consists only of black nodes is a red–black tree.
B.
I think this is valid, but I am not sure since there two adjacent red nodes?
有效。红色节点是兄弟节点是没有问题的。他们只是不应该处于亲子关系中。
C.
I think this is valid, but I am not sure since there two adjacent red nodes?
这是无效的。不是因为相邻的红色节点，而是因为属性 5。标签为 12 的节点有路径到其具有不同数量黑色节点的叶子。节点 25 也是如此。
作为一般规则，一个红色节点永远不可能只有一个 NIL-leaf 作为子节点。它的 child 要么都是 NIL-leaves，要么都是(黑色)内部节点。这是从属性得出的。
D.
I think this is not valid since it violate Property 4?
没有违反属性 4:红色节点的子节点是 NIL 叶子(此处未可视化)，它们是黑色的。这些红色节点具有黑色 NIL 叶子作为 sibling 的事实是无关紧要的:没有关于 sibling 的规则。所以这是有效的。
有关结合树 C 和 D 特征的示例，请参阅 Wikipedia article 中描述的这棵有效树。 ，它也描绘了 NIL 叶子:
关于algorithm - 红黑树的性质，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69517818/