binary-tree - 如何判断二叉树是否是红黑平衡的？

Question

在过去的一次考试中，我们曾经被要求通过查看树的形状来判断一棵树是否是红黑平衡的。我还没有找到任何关于如何做到这一点的信息，除了有人声称如果最长路径不超过最短路径的两倍，二叉树是红黑平衡的，但我很确定这是 null 的要求路径平衡树也是如此。那是对的吗？有没有办法通过形状判断一棵树是否是红黑平衡的？

Answer 1

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

A red-black tree is a binary tree that satisfies the following red-black properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.