大战红黑树

1.概念
2.性质
3.预备知识-旋转
- 3-1.左旋
- 3-2.右旋
4.预备知识-寻找节点的后继
5.插入调整
6.删除调整
7.总结

1.概念

红黑树(R-B Tree), 全称Red-Block Tree. 它是一种特殊的二叉树, 树中的每个节点都有颜色, 可以是红可以是黑.

注意: 非红色节点就是黑色节点, 即NULL节点是黑色节点

学习时可以先按照既定的规则进行调整, 学会后, 再去思考为什么有这些情况, 然后再考虑为什么这种情况需要这么处理.

2.性质

性质1: 节点是红色或黑色.
性质2: 根节点是黑色.
性质3: 每个NULL节点是黑色.
性质4: 每个红色节点的两个孩子节点一定是黑色.
性质5: 从任意节点到其NULL节点的所有路径中都包含相同数目的黑色节点.

3.预备知识-旋转

当红黑树的结构发生改变时(添加/删除元素), 红黑树的性质可能会被破坏, 需要通过调整使树重新成为红黑树, 调整可以分为两类:

颜色调整: 改变节点的颜色
结构调整: 左旋 + 右旋

3-1.左旋

左旋要确定对谁(旋转节点)进行左旋.

简单说: 左旋就是把旋转节点变为其右孩子的左节点(右孩子变为旋转节点的父节点).

3-1-1.左旋步骤

将旋转节点的右节点的左节点指向旋转节点的右节点上(双向关联).
将旋转节点的右节点的父节点指向旋转节点的父节点(双向关联).
将旋转节点的父节点指向旋转节点的右节点(双向关联).

3-1-2.左旋示例图

假设旋转节点为: 节点20, 对旋转节点进行左旋. 如下图

3-1-3.参考TreeMap的左旋代码

/** From CLR */
private void rotateLeft(Entry<K,V> p) {

	if (p != null) {

		// 获取p的右节点r, 临时存储
		Entry<K,V> r = p.right;

		// --将旋转节点的右节点的左节点指向旋转节点的右节点上(双向关联).
		// 将p的右节点的左节点连接到p的右节点上
		p.right = r.left;
		// 将p的右节点的左节点的父节点指向为p
		if (r.left != null)
			r.left.parent = p;

		// 将旋转节点的右节点的父节点指向旋转节点的父节点(双向关联).
		// 将p的父节点赋值给r, r的父节点指向为p的父节点
		r.parent = p.parent;

		if (p.parent == null) // 父节点为空, 根节点即为 r
			root = r;
		else if (p.parent.left == p) // p是父节点的左节点
			p.parent.left = r;
		else  // p是父节点的右节点
			p.parent.right = r;

		// 将旋转节点的父节点指向旋转节点的右节点(双向关联).
		r.left = p;
		p.parent = r;
	}
}

3-2.右旋

右旋要确定对谁(旋转节点)进行右旋.

简单说: 右旋就是把旋转节点变为其左孩子的右节点(左孩子变为旋转节点的父节点).

3-2-1.右旋步骤

将旋转节点的左节点的右节点指向旋转节点的左节点上(双向关联).
将旋转节点的左节点的父节点指向旋转节点的父节点(双向关联).
将旋转节点的父节点指向旋转节点的左节点(双向关联).

3-2-2.右旋示例图

假设旋转节点为: 节点30, 对旋转节点进行右旋. 如下图

3-2-3.参考TreeMap的右旋代码

/** From CLR */
private void rotateRight(Entry<K,V> p) {

	if (p != null) {

		// 临时存储p的左节点
		Entry<K,V> l = p.left;

		// 将旋转节点的左节点的右节点指向旋转节点的左节点上(双向关联).
		p.left = l.right;
		if (l.right != null)
			l.right.parent = p;

		// 将旋转节点的左节点的父节点指向旋转节点的父节点(双向关联).
		l.parent = p.parent;
		if (p.parent == null)
			root = l;
		else if (p.parent.right == p)
			p.parent.right = l;
		else p.parent.left = l;

		// 将旋转节点的父节点指向旋转节点的左节点(双向关联).
		l.right = p;
		p.parent = l;
	}
}

4.预备知识-寻找节点的后继

当节点元素被删除时, 如果待删除节点有两个孩子, 则不能删除该节点, 应该寻找到待删除节点的前驱或后继节点, 然后使用前驱或后继节点中值覆盖待删除节点的值, 最后把前驱或后继节点删除.

实际上节点的后继节点就是红黑树按照中序遍历结果, 节点元素的后一个元素, 前驱节点同理.

理解了二叉树的中序遍历, 这里边很容易理解了.

参考TreeMap的寻找后继代码:

/**
 * Returns the successor of the specified Entry, or null if no such.
 */
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {

	if (t == null) // null is null
		return null;
	else if (t.right != null) { // 右节点非空

		// 循环寻找右节点的左节点的左节点..., 直到左节点的左节点为null, 返回.
		Entry<K,V> p = t.right;
		while (p.left != null)
			p = p.left;
		return p;
	} else { // 右节点为null

		// t是父节点的右节点: 一直获取父节点, 直到获取到根节点, 返回
		// t是父节点的左节点: 后继节点就是父节点, 返回
		Entry<K,V> p = t.parent;
		Entry<K,V> ch = t;
		while (p != null && ch == p.right) {
			ch = p;
			p = p.parent;
		}

		return p;
	}
}

当然TreeMap中还有寻找节点的前驱的方法: Entry<K,V> predecessor(Entry<K,V> t).

5.插入调整

红黑树的插入操作如同二叉排序树的插入操作一样, 不同的时, 在新元素插入之后, 需要对数进行调整使其重新成为一颗红黑树, 这里就研究如何进行调整.

新插入的元素一定是叶节点, 那么父节点为黑色就不需要进行处理, 因为新插入的元素默认染为红色, 如果父节点是红色, 就违反了性质4, 此时需要进行调整.

5-1.插入新元素时会出现的情况

情况1: 红黑树是空树
情况2: 父节点为黑色
情况3: 父节点为红色 & 叔叔节点为红色
情况4: 父节点为红色 & 叔叔节点为黑色

5-2.情况1: 红黑树是空树

处理步骤:

将新节点染为红色
将新节点染为黑色

调整完成.

示例图

5-3.情况2: 父节点为黑色

父节点是黑色, 添加一个红色孩子节点并不会影响红黑树的性质, 不需要调整.

示例图

在只有根节点(20)的红黑树中插入一个新节点(10), 如下图

大家可以尝试一下在复杂的树中插入, 也不会影响红黑树的性质的.

5-4.情况3: 父节点为红色 & 叔叔节点为红色

处理步骤:

将父节点和叔叔节点染为黑色
将祖父节点染为红色

按照上述步骤调整之后, 祖父节点的颜色由黑色变为红色, 这时需要对祖父节点进行调整.

示例图

在现有的红黑树中插入新节点(35), 则调整过程如下

图中祖父节点即为根节点, 直接染为黑色即可, 如果祖父节点非根节点, 此时需要将当前节点指向祖父节点, 对祖父节点进行进一步的调整.

5-5.情况4: 父节点为红色 & 叔叔节点为黑色

处理步骤(父节点是祖父节点的左节点):

将新节点调整为父节点的左孩子节点(如果是父节点的右孩子的话)
1. 将父节点作为新节点
2. 对新节点进行左旋
将父节点染为黑色
将祖父节点染为红色
对祖父节点进行右旋

处理步骤(父节点是祖父节点的右节点):

将新节点调整为父节点的右孩子节点(如果是父节点的左孩子的话)
1. 将父节点作为新节点
2. 对新节点进行右旋
将父节点染为黑色
将祖父节点染为红色
对祖父节点进行左旋

发现, 节点的调整只在以祖父节点为根的树中进行调整, 调整前后祖父节点的颜色不变, 只要把以祖父节点为根的树调整为红黑树即可. 但是要保证调整前与调整后, 从祖父节点从叶节点的路径要包含相同数目的黑节点.

所以, 经过该步骤调整之后, 树一定为红黑树.

示例图

在现有的红黑树中插入新节点(45), 则调整过程如下

调整完成.

5-6.插入调整总结

插入调整总体看起来比较简单, 闭眼冥想一下各种情况, 然后接下来看代码.

5-7.参考TreeMap的插入调整代码

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {

	// 默认新节点的颜色为红色, 默认红色处理起来比较简单, WHY?
	x.color = RED;

	// 父节点为红色时, 增加一个新节点, 会违反性质4
	while (x != null && x != root && x.parent.color == RED) {

		if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 父节点为祖父节点的左节点

			// 获取叔叔节点
			Entry<K,V> y = rightOf(parentOf(parentOf(x)));

			if (colorOf(y) == RED) { // 叔叔节点为红色时

				// 父节点和兄弟节点染为黑色
				setColor(parentOf(x), BLACK);
				setColor(y, BLACK);

				// 祖父节点染为红色
				setColor(parentOf(parentOf(x)), RED);

				// 当前节点指向为祖父节点
				// 如果此时x=root了, 那么方法的最后一行代码便很有必要了.
				x = parentOf(parentOf(x));
			} else { // 叔叔节点为黑色时

				// 将新节点调整为父节点的左孩子节点
				if (x == rightOf(parentOf(x))) {
					x = parentOf(x);
					rotateLeft(x);
				}

				// 父节点染为黑色
				setColor(parentOf(x), BLACK);

				// 祖父节点染为红色
				setColor(parentOf(parentOf(x)), RED);

				// 对祖父节点进行右旋
				rotateRight(parentOf(parentOf(x)));

				// 此时, x的父节点已经被染为黑色了, 退出while循环
			}
		} else { // 与上面对应
			Entry<K,V> y = leftOf(parentOf(parentOf(x)));
			if (colorOf(y) == RED) {
				setColor(parentOf(x), BLACK);
				setColor(y, BLACK);
				setColor(parentOf(parentOf(x)), RED);
				x = parentOf(parentOf(x));
			} else {
				if (x == leftOf(parentOf(x))) {
					x = parentOf(x);
					rotateRight(x);
				}
				setColor(parentOf(x), BLACK);
				setColor(parentOf(parentOf(x)), RED);
				rotateLeft(parentOf(parentOf(x)));
			}
		}
	}

	// 最后将根节点染为黑色
	root.color = BLACK;
}

6.删除调整

删除, 对于红黑树来说是最复杂的, 也比较难理解, 分情况进行分析, 就简单了.

Let's go!

6-1.删除节点时会出现的情况

情况1: 节点既有左子树又有右子树
情况2: 节点只有左子树或只有右子树
情况3: 节点既没有左子树又没有右子树(节点是叶节点)

对于情况1, 我们首先要找到该节点的前驱或后继节点, 使用前驱或后继节点的值覆盖待删除节点的值, 然后将前驱或后继节点按照情况2或情况3进行删除即可, 此时前驱或者后继节点顶多有一个子节点. 本文中使用后继.

所以, 对于红黑树来说, 实际删除节点的情况只有两种(情况2和情况3), 但是这两种情况又分为多种情况, 下面一一列举.

下文中, 待删除节点用节点D(Delete)表示.

6-2.情况2出现的情况

情况2-1: 节点D是红色 & 其右节点(R)是黑色 -- 不存在
情况2-2: 节点D是红色 & 其右节点(R)是红色 -- 不存在
情况2-3: 节点D是红色 & 其左节点(L)是黑色 -- 不存在
情况2-4: 节点D是红色 & 其左节点(L)是红色 -- 不存在
情况2-5: 节点D是黑色 & 其右节点(R)是黑色 -- 不存在
情况2-6: 节点D是黑色 & 其右节点(R)是红色
情况2-7: 节点D是黑色 & 其左节点(L)是黑色 -- 不存在
情况2-8: 节点D是黑色 & 其左节点(L)是红色

分析情况2, 只会存在情况2-6和情况2-8的删除, 其它情况并不符合红黑树的特性, 所以根本不会存在其它情况的删除, 再看情况2-6和情况2-8, 由于节点D顶多有一个孩子, 所以两种情况的处理方式是一样的.

6-2-1.情况2-6: 节点D是黑色 & 其右节点(R)是红色

处理步骤:

将其右节点链接到其父节点上.
将其右节点染为黑色即可.

等同于删除了一个红色节点, 并不影响红黑树的性质.

示例图

在现有的红黑树中删除节点30, 过程如下

此时, 只需把节点删除, 然后把其后继节点染为黑色即可.

6-2-2.情况2-8: 节点D是黑色 & 其左节点(L)是红色

处理步骤:

将其左节点链接到其父节点上.
将其左节点染为黑色即可.

等同于删除了一个红色节点, 并不影响红黑树的性质.

示例图

如同情况2-6的示例图, 只不过孩子节点在左边而已.

6-3.情况3出现的情况

情况3-1: 节点D是红色
情况3-2: 节点D是黑色 & 兄弟节点是红色
情况3-3: 节点D是黑色 & 兄弟节点是黑色 & 兄弟节点有孩子节点
情况3-3: 节点D是黑色 & 兄弟节点是黑色 & 兄弟节点无孩子节点

6-3-1.情况3-1: 节点D是红色

此时父节点一定为黑色, 如果有兄弟节点, 兄弟节点一定为红色.

示例图

在现有的红黑树中删除节点35, 过程如下

删除一个红色节点并不会影响红黑树的性质, 无须调整.

6-3-2.情况3-2: 节点D是黑色 & 兄弟节点是红色

此时, 兄弟节点一定有两个黑色子节点, 因为节点D是叶节点.

处理步骤(节点D是父节点的左节点):

父节点染为红色
兄弟节点染为黑色
对父节点进行左旋
重新计算兄弟节点

处理步骤(节点D是父节点的右节点):

父节点染为红色
兄弟节点染为黑色
对父节点进行右旋
重新计算兄弟节点

示例图

在现有的红黑树中删除节点10, 过程如下

虚线表示节点被删除了, 经过该步骤之后, 树还不是红黑树, 需要进一步调整.

6-3-3.情况3-3: 节点D是黑色 & 兄弟节点是黑色 & 兄弟节点的子节点至少一个为红色

兄弟节点的子节点包括孩子节点和NULL节点, 因为它们都是黑色.

处理步骤(节点D是父节点的左节点):

将兄弟节点的红色子节点调整为兄弟节点的右节点(如果兄弟节点的右节点是黑色)
1. 将兄弟节点的左节点染为黑色
2. 将兄弟节点染为红色
3. 对兄弟节点进行右旋
4. 重新计算兄弟节点
将兄弟节点的颜色染为父节点的颜色
将父节点染为黑色
将兄弟节点的右节点染为黑色
对父节点进行左旋

处理步骤(节点D是父节点的右节点):

将兄弟节点的红色子节点调整为兄弟节点的左节点(如果兄弟节点的左节点是黑色)
1. 将兄弟节点的右节点染为黑色
2. 将兄弟节点染为红色
3. 对兄弟节点进行左旋
4. 重新计算兄弟节点
将兄弟节点的颜色染为父节点的颜色
将父节点染为黑色
将兄弟节点的右节点染为黑色
对父节点进行右旋

如果兄弟节点有两个红色子节点, 直接从第2步开始调整, 如果兄弟节点有一个红色子节点, 需要先将红色子节点调整为与兄弟节点方向一致的位置.

发现, 节点的调整只在以父节点为根的树中进行调整, 调整前后父节点的颜色不变, 只要把以父节点为根的树调整为红黑树即可. 但是要保证调整前与调整后, 从父节点从叶节点的路径要包含相同数目的黑节点.

所以, 经过该步骤调整之后, 树一定为红黑树.

示例图

在现有的红黑树中删除节点25, 过程如下

调整完之后便是红黑树.

6-3-4.情况3-4: 节点D是黑色 & 兄弟节点是黑色 & 兄弟节点的子节点都为黑色

兄弟节点的子节点包括孩子节点和NULL节点, 因为它们都是黑色.

处理步骤:

将兄弟节点染为红色
将待调整的节点指向父节点

这种情况删除节点D之后, 如果父节点是红色, 直接把父节点染为黑色, 兄弟节点染为红色即可. 如果父节点是黑色, 删除后经过父节点的路径少了一个黑节点, 需要对父节点进行调整.

示例图

在现有的红黑树中删除节点10, 过程如下

图中的情况是父节点是红色的情况, 如果父节点是黑色呢? 看下图

注: D表示待删除节点; X表示当前节点.

图中也只是演示了一种情况, 可以会出现其它情况, 但是任何情况也会坐落于删除的这几种情况之中.

6-4.删除调整总结

删除时, 先看待删除节点的颜色, 再看其兄弟节点的颜色, 最后看兄弟节点是否有子节点, 根据具体的情况进行调整.

6-5.参考TreeMap的删除调整代码

/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {

	// 删除的节点为黑色时, 需要进行调整
	while (x != root && colorOf(x) == BLACK) {

		// 当前节点是左节点
		if (x == leftOf(parentOf(x))) {

			// 获取右节点(兄弟节点)
			Entry<K,V> sib = rightOf(parentOf(x));

			// 兄弟节点是红色时
			if (colorOf(sib) == RED) {

				// 兄弟节点染为黑色
				setColor(sib, BLACK);

				// 父节点染为红色
				setColor(parentOf(x), RED);

				// 对父节点进行左旋
				rotateLeft(parentOf(x));

				// 重新计算兄弟节点
				sib = rightOf(parentOf(x));
			}

			if (colorOf(leftOf(sib))  == BLACK &&
				colorOf(rightOf(sib)) == BLACK) {  // 兄弟节点的两个子节点都是黑色, 其实是NULL节点

				// 兄弟节点染为红色
				setColor(sib, RED);

				// 将当前节点指向父节点
				x = parentOf(x);
			} else { // 兄弟节点的有子节点

				// 将兄弟节点的红色子节点调整为兄弟节点的右节点
				if (colorOf(rightOf(sib)) == BLACK) {
					setColor(leftOf(sib), BLACK);
					setColor(sib, RED);
					rotateRight(sib);
					sib = rightOf(parentOf(x));
				}

				// 将兄弟节点的颜色染为父节点的颜色
				setColor(sib, colorOf(parentOf(x)));

				// 父节点染为黑色
				setColor(parentOf(x), BLACK);

				// 兄弟节点的右孩子染为黑色
				setColor(rightOf(sib), BLACK);

				// 对父节点进行左旋
				rotateLeft(parentOf(x));

				// 调整完成, 退出循环
				x = root;
			}
		} else { // symmetric
			Entry<K,V> sib = leftOf(parentOf(x));

			if (colorOf(sib) == RED) {
				setColor(sib, BLACK);
				setColor(parentOf(x), RED);
				rotateRight(parentOf(x));
				sib = leftOf(parentOf(x));
			}

			if (colorOf(rightOf(sib)) == BLACK &&
				colorOf(leftOf(sib)) == BLACK) {
				setColor(sib, RED);
				x = parentOf(x);
			} else {
				if (colorOf(leftOf(sib)) == BLACK) {
					setColor(rightOf(sib), BLACK);
					setColor(sib, RED);
					rotateLeft(sib);
					sib = leftOf(parentOf(x));
				}
				setColor(sib, colorOf(parentOf(x)));
				setColor(parentOf(x), BLACK);
				setColor(leftOf(sib), BLACK);
				rotateRight(parentOf(x));
				x = root;
			}
		}
	}

	// 将x染为黑色
	setColor(x, BLACK);
}

7.总结

红黑树是一个比较重要的算法, 我觉得作为一个程序员应该需要了解它.

红黑树的核心在于元素变动之后, 如何进行调整使其重新成为一颗红黑树.

通过学习红黑树, 深刻体会到大问题并不可怕, 一点点拆分为小问题, 一定会解决的.

如有发现错误, 烦请指出.