红黑树的算法原理及讲解

红黑树原理和算法详细介绍

红黑树定义：

(1) 每个节点或者是黑色，或者是红色。

(2) 根节点是黑色。

(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]

(4) 如果一个节点是红色的，则它的子节点必须是黑色的。

(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

证明

首先定义一个节点x的黑高为b h ( x ) bh(x)bh(x),表示从x到任意一个叶子节点路径上黑色节点的个数（不包括x）。

1.第一步，先证明以某一节点x为根的子树中至少包含2 b h ( x ) − 1 2^{bh(x)}−12

bh(x)−1个内节点(不是叶子的都是内节点)。用数学归纳法证明。

如果x的高度为0，那么x是叶节点，包含0个内节点，满足该式子。

对于高度为正值的x，其两个孩子至少包含2 b h ( x ) − 1 − 1 2^{bh(x)−1}−12 bh(x)−1−1个内节点，

所以以x为根的子树至少包含( 2 b h ( x ) − 1 − 1 ) + ( 2 b h ( x ) − 1 − 1 ) + 1 = 2 b h ( x ) − 1 (2^{bh(x)−1}−1)+(2^{bh(x)−1}−1)+1=2^{bh(x)}−1(2bh(x)−1−1)+(2

bh(x)−1−1)+1=2bh(x)−1个内节点。

2.第二步，对于一棵高度为h的树，任意一条从根到叶节点（不包括根）的路径上至少有一半黑色节点，从而b h ( x ) ≥ h / 2 bh(x)≥h/2bh(x)≥h/2，所以n ≥ 2 b h ( x ) − 1 ≥ 2 h / 2 − 1 n≥2^{bh(x)}−1≥2^{h/2}−1n≥2bh(x)−1≥2h/2−1，即h ≤ 2 l o g ( n + 1 ) h≤2log(n+1)h≤2log(n+1)