红黑树相关定理及其证明

红黑树有一条性质要求：如果一个节点为红色的，则它的两个子节点都是黑色。这保证了：从根到叶节点（不包括根节点）的任何一条路径上都至少有一半的节点是黑色的。（红黑树的性质还要求：对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点）。

0. 明确一些基本概念

• 树的深度和高度：
  
  • 树的深度是从根节点开始（其深度为1）自顶向下逐层累加的，而高度是从叶节点开始（其高度为1）自底向上逐层累加的。

1. 证明：一棵有 n 个内部节点的红黑树的高度至多为 2lg(n+1)

• 该定理表明了内部节点与树高之间的关系；
• 也即，在红黑树中，内部节点的数量实现了对红黑树高度的约束，使之尽可能的平衡。

首先证明，任意节点 x 为根的子树（递归定义）中至少（≥）包含 2bh(x)−1 个内部节点（n≥2bh(x)−1）。欲证明这点，采用归纳法。

• x 的高度为 0，即 x 为叶节点 （T.nil，只有叶节点的高度为 0），则以 x 为根节点的子树至少包含 2bh(x)−1=20−1=0 个内部节点。
• 考虑 x 的高度为正值，且有两个子节点的内部节点 x，则其每个子节点有黑高 bh(x) 或 bh(x)−1（取决于自身的颜色是红 bh(x)，还是黑 bh(x)−1），则根据归纳法的假设，每个子节点至少有 2bh(x)−1−1 个内部节点（2bh(x)−1、2bh(x)−1−1），
  
  • 于是，它们的父节点以 x 为根的子树至少包含：(2bh(x)−1−1)+(2bh(x)−1−1)+1=2bh(x)−1（左侧的+1，加的是 x，根节点也属于内部节点）

还需引入输的高度 h，由红黑树的性质：如果一个节点为红色，则它的两个字节点都是黑色，可知，从根到叶节点（不包括根节点）的任何一条简单路径都至少有一半的节点为黑色，也即黑高至少是树的半。

n≥2bh(x)−1⇓n≥2bh(x)−1≥2h/2−1⇒n≥2h/2−1⇓h≤2log(n+1)

2. 最长路径至多是最短路径的两倍

在一棵红黑树中，从某节点 x 到其后代叶节点的全部简单路径中，最长的一条至多是最短一条的 2 倍。

• 设最长的路径为 (a1,a2,…,as)
  
  • 由红黑树的性质：如果一个节点是红色节点，则其两个子节点为黑色节点，⇒ 这条简单路径上至少一半的节点为黑色；
    
    • 则红色节点的数量：≤⌊s−12⌋，因此黑色节点的数量至少为：≥⌈s+12⌉
• 设最短的路径为 (b1,b2,…,bt)

又由红黑树的任何一条简单路径的黑高相同，因此，t≥⌈s+12⌉。然后通过反证法进行证明，s>2t 所以有：

t≥⌈s+12⌉≥⌈2t+12⌉=t+1

出现矛盾。

3. 内部节点最多，内部节点最少

如果一棵红黑树的黑高为 k，则其内部节点最多为，做少为：

• 内部节点最多时的情形为：任何一个简单路径上，黑红黑红黑宏，的循环排列，
  
  • 此时红色节点数目达到最大，树高也达到最大，最大为：2k+1，此时内部节点为：22k+1−1
• 内部节点最少时的情形为：全部均是黑色节点的完全二叉树；
  
  • 此时红色节点数目为 0，树高达到最低，为：k+1
  • 内部节点数量为：2k+1−1