以下哪些是有效的红黑树？

红黑树的性质：

根据性质，这些红黑树是有效还是无效？

我认为这是有效的

我认为这是有效的，但我不确定，因为有两个相邻的红色节点？

D。

我认为这是无效的，因为它违反了属性 4？

我理解 RBtree 的这些属性了吗？如果不是，我哪里错了？

4
投票

您已经正确列出了红黑树的属性。在这四棵树中，只有 C 不是有效的红黑树：

A.

这是一棵有效的树。维基百科确认：

每一个仅由黑色节点组成的完美二叉树都是红黑树。

B.

我认为这是有效的，但我不确定，因为有两个相邻的红色节点？

有效。红色节点是兄弟节点没有问题。他们只是不应该处于亲子关系中。

C.

我认为这是有效的，但我不确定，因为有两个相邻的红色节点？

无效。不是因为相邻的红色节点，而是因为属性 5。标签为 12 的节点具有到其叶子节点的路径，其中黑色节点的数量不同。节点 25 也是如此。

作为一般规则，红色节点永远不可能只有一个 NIL 叶作为子节点。它的子节点要么都是 NIL 叶子，要么都是（黑色）内部节点。这是从属性中得出的。

D。

我认为这是无效的，因为它违反了属性 4？

性质 4 没有被违反：红色节点的子节点是 NIL 叶子（此处未可视化），它们是黑色的。这些红色节点作为兄弟节点具有黑色的 NIL 叶子这一事实是无关紧要的：没有涉及兄弟节点的规则。所以这是有效的。

有关结合树 C 和 D 的特征的示例，请参阅维基百科文章中描述的有效树，该文章还描述了 NIL 叶子：

2
投票

A、B 和 D 是有效的红黑树

C 不是有效的红黑树，因为从根到叶的黑色高度不一样。某些路径为 2，其他路径为 1。它违反了您所说的规则 5。

如果 12 有一个黑色的右孩子，25 有一个黑色的左孩子，那么它将是一棵红黑树。

0
投票

红黑树与2-3-4树（4-B树）基本相同，尽管分裂/交换方法是颠倒的。 2-3-4 树具有固定大小的 3 节点桶。黑色意味着它是 3 桶的中心节点。任何红黑树都被视为具有空节点（黑洞和红洞）的完美四叉树/二叉树（3节点桶）。

换句话说，每个黑色节点（每个 3-bucket）在完美树中都有其绝对位置（2 维唯一笛卡尔或 4-adic/2-adic 唯一分数数）。

NIL 节点只是额外的标志以节省空间；您没有足够的内存来存储完美的四叉树/二叉树。

检查红黑树最简单的方法是检查每个黑色节点是否是一个新的桶（向下），并且每个红色节点都与上面的黑色节点（同一桶）分组。如果中央黑色节点的红色节点少于 2 个，您可以在中央黑色节点旁边（左和右）添加空的红色孔。

新的黑色节点始终是最后一个黑色节点的孙子，每个黑色节点只能有两个红色子节点，不能有黑色子节点。如果红色女儿（母亲）为空（死亡/未出生），则无母亲的孙子节点直接链接到其祖父节点。

一个没有母亲的黑色孙子节点没有兄弟，但他旁边可以有一个黑色表弟节点；这两个堂兄弟姐妹与同一个祖父有联系。

四叉树是二叉树的子集。

所有黑色节点的高度均为偶数（2,4,6...），所有红色节点的高度为奇数（1,3,5...）。您也可以选择使用半个单位 0.5。

3桶的尺寸固定为3；只需添加额外的红孔（未出生的未连接的红色女儿）即可制成 3 号。