Thinking in Data Structure -- 红黑树（思考）

红黑树，是二叉搜索树的一种。跟 AVL树 都属于平衡二叉树。我们将一棵树定义为红黑树当且仅当其满足下面的性质：

1. 树的节点要么是黑的，要么是红的
2. 树的根节点是黑的
3. 树的叶节点是黑的
4. 如果一个节点的颜色是红的，那么它的两个儿子的颜色都是黑的
5. 对于每一个节点，从该节点（不包含该节点本身）到其所有后代叶节点的简单路径，均包含相同数目的黑色节点。该数目称为 黑高。

需要注意一点的是，与普通的树不同，红黑树的叶节点不是出度为零的节点，而是空节点的另一个说法。或者说，如果一个节点的某一个子节点为空，那么该子节点就是一个叶节点。

在上面的 5 个性质中，第 5 点是保证红黑树的平衡性的关键。这里涉及到一些数学上的证明，《算法导论》里面有，我会在别的文章中进行适当的说明，这里先跳过。

然后是红黑树的一系列操作，查询的我就不说了，跟二叉搜索树是一模一样的，这里重点说一下更新操作 – 插入和删除

插入

首先，插入的第一步是找到要插入的位置，这一点跟二叉搜索树是一样的。但是接下来就有问题了，红黑树的节点都是有颜色的，那么新的节点的颜色应该是什么呢？然后，插入新节点之后，上面的 5 个性质还能保持吗？

首先，新节点的颜色我们选择红色，因为从性质 5 我们知道，每一个节点的所有黑高都必须一样，而红节点并不影响黑高，所以选择红色将不会改变性质 5 。更重要的是，一旦某个节点的性质 5 被改变，那么所有包含该节点的性质 5 都将不符合，这样到来的代价将是巨大的。

但是，选择红色也会出现问题，那就是新节点的父节点如果是红色的，那么将违反性质 4 ，怎么办呢？所以，插入之后，我们必须进行调整，而插入的重点也就在这了。我们来看一下 《算法导论》 的伪代码(这是我自己写的，形式采用了类 C 的写法，不过思想是一样的)：

RB-Insert-FIX(T, x)

while x.p.color == RED
	if x.p.p.left == x.p		
		y = x.p.p.right
		if y.color == RED							//case 1
			x.p.color = y.color = BLACK	
			x.p.p.color = RED
			x = x.p.p
		else 
			if x = x.p.right						//case 2
				x = x.p
				LEFT_ROTATE(T, x)
			x.p.color = BLACK						//case 3
			x.p.p.color = RED
			RIGHT_ROTATE(T, x.p)
	else //(将上面的 left 和 right 互换即可)

	T.root.color = BLACK

从上面的伪代码我们可以看到，插入分为三种情形，这里我们将 y 称为 x 的叔节点，所以这三种情况可以这样分：

1. x 的叔节点是红色的
2. x 的叔节点是黑色的且 x 是父节点的右节点
3. x 的叔节点是黑色的且 x 是父节点的左节点

值得说明的是，我们在 RB-Insert-FIX 执行的过程中，x.p.color 一直都是红色的，这也是 RB-Insert-FIX 的循环条件，为什么是这样的呢？因为如果 x.p.color 是黑色的，那么根据我们前面提到的，插入的时候性质 5 是一直保持的，而性质 1,2,3 也是一直都保持的，唯一有可能违反的就是性质 4 了。如果 x.p.color 是黑的，那么性质 4 也将符合，那么说明整棵树满足性质 1-5，已经是一棵红黑树了。

然后我们来分析一下这三个 case：

• case 1: x 的叔节点和父节点都是红的，注意此时并不关心 x 是父节点的左儿子还是右儿子，选择的策略是将 x 的红色上移，具体做法是，将 x 的叔节点和父节点都赋值为黑色，x 的爷爷节点赋值为红色，并将 x 重新指向为 x 的爷爷节点。同时，现在的 x 节点的父节点也有可能是红的，循环将继续
• case 2: x 的叔节点是黑的且 x 是父节点的右儿子，这个 case 是为了将其转化为 case 3，然后统一处理。
• case 3: x 的叔节点是黑的且 x 是父节点的左儿子，这个 case 跟上面 case 2 的区别是，case 2 中 x，x.p，x.p.p 的排列是弯曲 zig-zag 型的，而 case 3 则是直线 zig-zig 型的。

具体操作就在那里，多看即便就可以理解，必须记住的是无论进行什么操作都是为了恢复被破坏的性质。

删除

相比插入而言，删除就难多了，不过也是个人觉得红黑树最出彩的地方了，进过一系列的操作之后，then it works! 确实不得不佩服前人的智慧！

红黑树的删除跟二叉搜索树的删除是差不多的，都是先找到该点所在的位置，然后根据其儿子的个数进行相应的变换。只不过多了一个恢复红黑性质的操作。

接下来，我想根据我看《算法导论》是遇到的问题以及我是如何解决这些问题的来说明删除这一操作。

首先，我们来看一下删除的伪代码：

RB-Delete(T, z)

y = z
y-initial-color = y.color
if z.left == T.nil
	x = z.right
	RB-TRANSPLANT(T, z, z.right)
else if z.right == T.nil
	x = z.left
	RB-TRANSPLANT(T, z, z.left)
else
	y = TREE-MINIMUN(z.right)
	y-initial-color = y.color
	x = y.right
	if y.p = z
		x.p = y
	else
		RB-TRANSPLANT(T, y, y.right)
		y.right = z.right
		y.right.p = y
	RB-TRANSPLANT(T, z, y)
	y.left = z.left
	y.left.p = y
	y.color = z.color

	if y-initial-color == BLACK
		RB-DELETE-FIX(T, x)

这里要注意的是，x 这个变量的含义是：

如果 y 的某个儿子非空，那么 x 总是指向 y 非空的儿子，并且在 RB-TRANSPLANT 执行之后指向 y 原来的位置。之所以是这样我们可以注意到 RB-TRANSPLANT 这个函数的第三个参数总是跟 x 相等的。否则，y 的两个儿子皆为空，那么 x 指向 y 的右儿子，并且在 RB-TRANSPLANT 执行之后指向 y 原来的位置，原因跟上面的一样。

同时，要注意到 x.p 的赋值，当 y.p != z 时，x.p 总是指向 y 的父节点，而且该过程是在 RB-TRANSPLANT 的最后一句实现的。当 y.p == z 时，x.p 将赋给 y。为什么是这样呢？这是因为当 z 有两个儿子的时候且 y.p != z 时，y 就是 z 的后继（跟二叉搜索树是一样的），此时需要进行的操作是：x 代替 y，y 接手 z 的右儿子，y 代替 z，y 接手 z 的左儿子，所以此时 x.p 将指向 y 的父节点。但是，如果 y.p == z 的话，只需要将 y 直接替代 z 并且接手 z 的左儿子，y 的右儿子（即 x）依旧保持不变，所以 x.p 将指向 y 。

还有要注意，这里的删除相当于一种 lasy delete，当 y == z 时，只是将 z 的父节点指向 z 的非空儿子而已；当 y != z
时，它只是将 y 的值赋给 z 的值，z 的颜色将保持不变，这一点很重要！

最后，注意到调用 RB-DELETE-FIX 的条件是：y-initial-color == BLACK 。为什么是这样呢？因为如果 y 是红色的，删除它并不影响黑高。要阐述这一点，得分情况讨论：

1. y == z. 这种情况是在 z 的儿子数小于 2 的时候。又因为 z 的某一个儿子为空，所以左右黑高都为 1，且由于 z == y 为红节点，所以只可能是左右都为空，此时 x 为叶节点，替代 y 后，黑高仍为 1 。

2. y != z. 这种情况发生在 z 的儿子树为 2 且 z.right == T.nil 的时候。前面提到，这种情况下的删除只是将 y 的值赋给 z 而已，z 的颜色并没有改变，所以这种情况下相当于在树中删掉一个红节点，而且，因为这种情况下 y 的左儿子必为空（可分为两种情况讨论，y.p == z 或者 y 是 z 的后继），所以黑高必为 1 。删掉该红节点之后，因为 T.nil 的黑高也为 1，所以性质 5 没有违背，不需要修复！

接下来，就是删除的重点——RB-DELETE-FIX 了，我们先来看一下伪代码：

RB-DELETE-FIX(T, x)

while x != T.root && x.color == BLACK
	if x == x.p.left
		w = x.p.right
		if w.color == RED											//case 1
			w.color = BLACK
			x.p.color = RED
			LEFT-ROTATE(T, x.p)
			w = x.p.right
		else if w.left.color == BLACK && w.right.color == BLACK     // case 2
			w.color = RED
			x = x.p
		else if w.right == BLACK									// case 3
			w.left.color = BLACK
			w.color = RED
			RIGHT_ROTATE(T, w)
			w = x.p.right
		w.color = x.p.color											// case 4
		x.p.color = x.right.color = BLACK
		LEFT_ROTATE(T, x.p)
		x = T.root
	else //（将上面的 left 和 right 调换即可）

x.color = BLACK

在这个过程中，有几个点要注意一下：

1. RB-DELETE-FIX 的循环条件是：x != T.root && x.color == BLACK，这里解释一下第二个条件。我们之所以需要这一个函数来修复红黑性，是因为删除掉一个黑节点将会导致部分子树的黑高减少，而 x 代替的是 y 原来的位置，所以如果 x.color == RED 的话，那么只需将 x.color 赋值成 BLACK 即可恢复性质 5 了。

2. 《算法导论》中提到只有 case 2 将会导致循环，我自己试了一下，发现确实是这样的，而且如果红黑树是一个所有节点都为黑色的满二叉树，那么 case 2 将会一直循环到根节点为止。

3. 有一个点要特别注意，就是 case 4 的第一句：w.color = x.p.color 。为什么要这样呢？那是因为 x.p.color 的值不知道，而且这步操作之后是要将原子树变成以 w 为根的新子树，而我们知道原子树的父节点以及其祖宗都是满足所有性质的，所以，如果 w 保持 x.p 原来的颜色而且满足了性质 5 ，那么，这棵树就满足红黑性了！

4. 最后，还是那一句。上面的所有操作都是为了让子树恢复红黑性，所以，主要是理解为主。虽然，我也为了理解每一步究竟为什么要这要做思考了很多，也有所收获，但是最后发现，这个东西真的只能理解，写是写不出来的，或者说，无法十分严谨地写出来，所以便作罢了。

好了，写得够多了。再一次说明，上面的所有内容都是我自己的思考，可能会有错，不过我会一直维护，希望能够为大家学习红黑树这个有用的数据结构带来一点帮助，那我也就心满意足了～

EOF