一个4节点的红黑树应该是什么样子的
What should a 4-node red-black tree look like
你好，我以前对红黑树知之甚少，也许这是一个愚蠢的问题。
这是一个 4 节点树：
它是合法的红黑树吗？
在我看来，它实际上违反了红黑树的规则：
- Every red node has both of its children colored black.
- Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.
如果不是，4 节点红黑应该是什么样子？
谢谢
你是对的，这棵树违反了红黑树的规则，因为路径3-2-1-Null经过3个黑色节点，而3-4-Null只经过2个。
回想一下，没有约束 black 节点必须将其子节点涂成 red，只有相反的情况。 Even a tree with all black nodes is technically a red-black tree，只要它是平衡的，因此满足“从根到树叶的每条路径都包含相同数量（'black-height'）的黑色节点。”
因此，您可以通过将节点 2 和 4 绘制为黑色并将节点 1 绘制为红色来使这棵树成为有效的红黑树。注意节点 1（唯一的红色节点）仍然有 2 个黑色子节点，并且从根到叶子的所有路径都会碰到 3 个黑色节点。因此满足红黑树的规则
你好，我以前对红黑树知之甚少，也许这是一个愚蠢的问题。
这是一个 4 节点树：
它是合法的红黑树吗？ 在我看来，它实际上违反了红黑树的规则：
- Every red node has both of its children colored black.
- Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.
如果不是，4 节点红黑应该是什么样子？
谢谢
你是对的，这棵树违反了红黑树的规则，因为路径3-2-1-Null经过3个黑色节点，而3-4-Null只经过2个。
回想一下，没有约束 black 节点必须将其子节点涂成 red，只有相反的情况。 Even a tree with all black nodes is technically a red-black tree，只要它是平衡的，因此满足“从根到树叶的每条路径都包含相同数量（'black-height'）的黑色节点。”
因此，您可以通过将节点 2 和 4 绘制为黑色并将节点 1 绘制为红色来使这棵树成为有效的红黑树。注意节点 1（唯一的红色节点）仍然有 2 个黑色子节点，并且从根到叶子的所有路径都会碰到 3 个黑色节点。因此满足红黑树的规则