问题及解答

定义: 红黑树(Red Black Tree) 是一种具有下列着色规则的二叉查找树:

1. 每一个结点或者是红色, 或者是黑色. (可以 标记为 0 和 1)
2. 根结点是黑色的.
3. 红色结点如果有儿子, 那么它的子结点必须是黑色的.
4. 从任何一个结点到一个 NULL 指针的每一条路径都必须包含相同数目的黑色结点.

证明: 结点数为 $N$ 的红黑树的高度至多是 $2\log(N+1)$. 

References:

Mark Allen Weiss 著, 张怀勇 等译 《数据结构与算法分析(C++描述)》（第3版）,  人民邮电出版社.