判断给定Red Black Tree是否平衡并讲解红黑树平衡理论

给定树的平衡判断 #

先明确给定的树结构（将None替换为红黑树标准的NIL空节点）：

10(黑节点)
                                       /          \
                              8(黑节点)       NIL(黑节点)
                              /           \
                      NIL(黑节点)   NIL(黑节点)

这棵树不平衡，核心原因是违反了红黑树的平衡约束：从任意节点到其所有后代叶子节点的路径上，黑节点的数量必须完全相等（即黑高一致）。具体对比：

• 根节点10到右侧NIL叶子的路径：黑节点为10、NIL，共2个
• 根节点10到左侧任意一个NIL叶子的路径：黑节点为10、8、NIL，共3个

两条路径的黑节点数量不同，直接破坏了红黑树的合法性。

其余红黑树规则的检查结果：

• 所有节点（包括NIL）均为黑色，满足“节点非红即黑”“叶子节点为黑”的要求
• 根节点是黑色，符合规则
• 无红节点，自然满足“红节点的子节点必须为黑”的规则
  但仅第五条平衡规则的违反，就足以判定这不是一棵合法的红黑树。

红黑树平衡相关核心理论 #

红黑树是一种自平衡二叉搜索树，通过以下五条规则强制维持近似平衡，确保树的高度始终处于O(log n)级别，保证高效的增删查性能：

• 规则1：每个节点要么是红色，要么是黑色
• 规则2：根节点必须是黑色
• 规则3：所有叶子节点（指NIL空节点，而非存储数据的节点）必须是黑色
• 规则4：如果一个节点是红色，那么它的两个子节点必须是黑色（不允许出现连续的红节点）
• 规则5：从任意一个节点到其所有后代叶子节点的路径上，黑色节点的数量完全相同（这条是平衡的核心约束）

规则如何实现平衡？
规则5保证了所有路径的黑高一致，结合规则4限制红节点连续，使得最长路径的长度最多是最短路径的2倍——最短路径全由黑节点组成，最长路径则是黑红交替出现。这种约束彻底避免了二叉搜索树退化为链表的情况，让红黑树始终保持高效的操作效率。

内容的提问来源于stack exchange，提问作者RezDom