如何判断二叉树是否为红黑平衡？

Question

在过去的考试中,我们曾经被要求通过观察它的形状来决定树是否是红黑平衡的.我没有找到任何有关如何执行此操作的信息,除非有一个视图声称如果最长路径不超过最短路径的两倍,则二叉树是红黑平衡的,但我很确定这是null的要求路径平衡的树木.那是对的吗？有没有什么方法可以判断一棵树的形状是红黑平衡的？

Answer 1

我不是大师，但这来自 Cormen 的书Introduction to Algorithms：

红黑树是满足以下红黑性质的二叉树：

1. 每个节点要么是红色，要么是黑色。
2. 根是黑色的。
3. 每片叶子（NIL）都是黑色的。
4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
5. 对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点。