红黑树相关定理及其证明
红黑树有一条性质要求：如果一个节点为红色的，则它的两个子节点都是黑色。这保证了：从根到叶节点（不包括根节点）的任何一条路径上都至少有一半的节点是黑色的。（红黑树的性质还要求：对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点）。
0. 明确一些基本概念
- 树的深度和高度：
- 树的深度是从根节点开始（其深度为1）自顶向下逐层累加的，而高度是从叶节点开始（其高度为1）自底向上逐层累加的。
- 该定理表明了内部节点与树高之间的关系；
- 也即，在红黑树中，内部节点的数量实现了对红黑树高度的约束，使之尽可能的平衡。
首先证明，任意节点 ）。欲证明这点，采用归纳法。
- 个内部节点。
- 考虑 ，根节点也属于内部节点）
还需引入输的高度 ，由红黑树的性质：如果一个节点为红色，则它的两个字节点都是黑色，可知，从根到叶节点（不包括根节点）的任何一条简单路径都至少有一半的节点为黑色，也即黑高至少是树的半。
2. 最长路径至多是最短路径的两倍
在一棵红黑树中，从某节点 到其后代叶节点的全部简单路径中，最长的一条至多是最短一条的 2 倍。
- 设最长的路径为
又由红黑树的任何一条简单路径的黑高相同，因此， 所以有：
出现矛盾。
3. 内部节点最多，内部节点最少
如果一棵红黑树的黑高为 ，则其内部节点最多为，做少为：
- 内部节点最多时的情形为：任何一个简单路径上，黑红黑红黑宏，的循环排列，
- 此时红色节点数目达到最大，树高也达到最大，最大为：
- 内部节点最少时的情形为：全部均是黑色节点的完全二叉树；
- 此时红色节点数目为 0，树高达到最低，为：
- 内部节点数量为：