4节点红黑树合法结构咨询与自定义结构合法性判定

先明确红黑树的核心规则（方便你对照验证）：

• 根节点必须是黑色
• 所有空叶子节点（NIL节点）默认是黑色
• 红色节点的父节点必须是黑色，且它的两个子节点也必须是黑色（禁止连续红色节点）
• 从任意节点到其所有后代空叶子的路径上，黑色节点的数量必须完全相同（黑高度一致）

1. 合法的4节点红黑树结构 #

这里的「4节点」指包含4个实际数据节点（不含NIL空节点）的红黑树，合法结构只有一类（含左右对称变体）：

标准结构示例 #

黑（根）
       /        \
    黑节点A    黑节点C
   /
红节点B

（所有未画出的子节点均为黑色NIL节点）

规则验证 #

• 根节点是黑色，符合要求
• 红色节点B的父节点是黑色A，子节点是黑色NIL，满足「红节点的子节点必须为黑」的规则
• 所有路径的黑高度一致：
  • 根 → A → B → NIL：黑色节点为「根、A、NIL」，共3个
  • 根 → A → NIL：黑色节点为「根、A、NIL」，共3个
  • 根 → C → NIL：黑色节点为「根、C、NIL」，共3个

当然，把红色节点B放在黑节点C的子节点位置（根的右侧分支），也是完全合法的，属于对称变体。

2. 你的自定义4节点树的合法性判断 #

根据你描述的情况——违反了「红节点的子节点必须为黑」和「黑高度一致」这两项核心规则，那你的自定义结构肯定不合法。

红黑树的规则是强约束，只要违反其中任意一条，就不再是合法的红黑树。要修正的话，你需要调整节点颜色和结构，使其符合上面提到的标准结构（或对称变体），确保所有规则都被满足。

内容的提问来源于stack exchange，提问作者C.Hu