RB Tree - 红黑树

之前的笔记

序

红黑树是一种非常常见的结构，但是网络上的文章很少将它的原理解释清楚，尤其是添加删除的情况的分类，这里将以前的笔记一起放上，正好方便读者了解，进程调度用了非常多的红黑树结构。

为什么能平衡

极端情况

红黑树的定义这里不赘述，同时我也不会讲解旋转的操作，因为这些有的是文章讲解。首先，我解释一点，红黑树的平衡来自哪里。

从根结点出发，任意一条的路径上的黑色节点数相等

那么极端情况就容易理解了，即一边全黑，另外一边红黑交替，也就是说，最短路径的长（高）度为 n，那么另外最长（高）的长（高）度为 2n，红黑树的容忍的树高差就是树高最小的值，所以它可以不那么平衡，这是跟 AVL树 的区别。

旋转如何能维持平衡

首先，旋转的本质只是节点的左移和右移，为的就是维护子树的树高平衡。

考虑上图的左旋，其实就是黑色节点跑到了左子树，原来在右子树的节点，跑到了根节点。宏观上理解，就是右子树的节点变少了，左子树的节点变多。非要理解，就是旋转点变为左节点，而旋转点的右节点变为父母，其左子树附加到旋转点右子树。多复杂，就用宏观理解，其实就是平衡树，而子树的移动是理所当然的。

这个也是如此，可能比较抽象，但最终的结果都是，旋转点到了子树，减少了一端的子树的高度，这就是旋转的实质。可能上面这幅图没有平衡的感觉，是的，实际操作，还要左旋一次，也就是左旋的图那样～

左旋即 旋转点到左子树，右子树树高减少，右旋亦同理。

红黑树的插入与删除

插入节点的步骤最开始和搜索二叉树相同，然后插入的节点是作为红色节点，然后如果树高不平衡，就需要调整（ rotate ），删除也类似，如果左右都有节点，则先找到它的后继（successor），两者替换位置后再删除，这样做的目的是选择一个只有单子树的位置，容易操作。

Insertion

第一步，按搜索树插入新节点，并标记新节点为红色

国外教授的课件

这个课件使用的是 edge 的说法，而不是我们平常说的节点颜色，其实是一样的。

一直忘了说，null 也算是黑色节点，其实不影响判断，因为每条路径下，最后必然是叶子节点，所以也必然都有 null，那么大家都会抵消了。

这里说明了一点，就是需要调整的时机，即出现了连续俩个红色的节点，也就是说，我们插入之后发现父母节点是红色，那么就得调整了。

如果父母是黑色，不用调整，看了之前的分析，其实决定“树高”的一直都是黑色节点，红黑树只需要保证，没有连续的红色节点，每条路径的黑色节点相同，所以这里不考虑父母是黑色结点的情况了。

插入新节点要考虑三代节点

g 指代 grandparent，p 指代 parent，还有一个节点，即 uncle，这是插入的时候要考虑的三个结点，当然，插入的节点本身一定是红色了。

一次旋转即可的情况

上面说明的是一个情况，即 uncle 是黑色，p 是红色，可以得到的一点，g 一定是黑色，因为只有黑色节点后面才可以跟红色节点。现在说明，这里右旋的原因，现在明显是 g->p->n 这一子树的树高会比 g->uncle 那一子树多（大多数正常情况下），首先，这俩条路径的黑色节点一定相同！这是RB tree 存在的意义，然后现在出现了连续俩个红色节点，违反了规则，其实就是 树高 已经不平衡了～

我们能做的一件事，就是把一个红色节点，移动到另外一条子树，能这样的做的理由就是，g 是黑色，u 是黑色，它们之间，起码还有一个红色节点的位置！

也说了旋转的实质，所以这里，g 直接右旋到右子树，然后发现，右旋导致了一点，看下图

这里的右旋，导致左子树的黑色节点，少了，右子树的黑色节点，多了。所以我们重新染色。

其实大多数情况下，uncle 应该是空节点，因为插入的节点的位置肯定是叶子，那么可以发现原来二叉树已经不平衡了，所以可以判断 U 是空节点，不过这里更加形象，所以画出。当然，最后一种情况可能导致这个结果，也就是，染色导致上层的不平衡（看 Uncle 是红色节点的部分 ）。

再给出，另外一个方向的情况，不在讨论了。

此处默认 U 是黑色节点

复杂的情况，不连成直线

当 N 是 P 的右节点，而 P 是 G 的左节点，或者反过来，即 G P N 不再是一条直线的时候，需要二次旋转，看下图。

发现了吗，经过一次旋转（以P为基准）之后，我们得到了前一种情况，只是现在 N 变成了 “P“，P 变成了 “N“，所以虽然说复杂，其实就是多了一步转换而已。给出转换图。

蓝色 表示新插入节点，是红色

看看教授的课件如何讲解的。

上图的是 left-right rotation，还有一个 right-left 其实我的图片已经有了，本质就是经过一次旋转后，转换为最早我们说的那个情况而已。

实际编写代码的时候，可以先处理这个情况，转换成上面的GPN连成直线的情况，这是代码编写的技巧。

稍微简单的情况，Uncle is Red

最简单的情况，当然就是父亲节点是黑色，什么都不处理，这里考虑 Uncle 不再是黑色，而是红色。

思考一会，现在 G U 之间，可没有位置安放一个红色节点了，如何是好？

答案是，交给上层处理，这其实说明，这一区域的树其实已经比较平衡了，没有较大的树高差，至于在往上，我们也不知道，所以传递上去，那么如何传递，且看。

实质是，左右得到一个黑色节点，然后把 G变为黑色，最后的结果是不多不少，但是 G 可能其父母是红色，所以，又转换为了之前的情况～ 看教授的课件是如何说明的。

所以，代码处理的过程中，为 G 变成了新的节点，重新再过函数处理流程一遍（即循环的 continue）

下面给出我画的一张图

N G P U没有标出，蓝色是新插入节点

总结

注意，旋转能解决的，必然是瞬间完成，只有 Uncle 是红色的时候，有可能一直向上传递，这样就有多次处理了。思考一个问题，黑色节点是如何增多的？

之前的处理，都是保证了黑色节点没有改变，其实是当旋转之后，发现旋转点是根结点，而现在的根结点又是红色，于是将根结点变为黑色，或者，向上传递之后，发现 G 就是根结点，而 G 现在是红色，所以变为黑色，就这样，黑色节点增加了。～

Kernel rbtree 注释

很多地方都用到了，红黑树结构，这里给出一些注释，其实红黑树的插入比较简单一些。

rbtree.c

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *parent, *gparent;

	while ((parent = rb_parent(node)) && rb_is_red(parent))
	{ /* 循环结束的标志， 父母存在（非根结点），父母是红色（黑色不用处理 ）*/
		gparent = rb_parent(parent);

		if (parent == gparent->rb_left)
		{
			{
				/* uncle is red， 直接染色，然后 continue */
				register struct rb_node *uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_right == node)
			{
				/* G P N 不在一条直线的情况， 旋转之后，N G 互换 */
				register struct rb_node *tmp;
				__rb_rotate_left(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}
			/* 一条直线的情况， 旋转之后染色，重新处理  */
			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_right(gparent, root);
		} else {
			/* 镜面操作，不在解释 */
			{
				register struct rb_node *uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_left == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_right(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_left(gparent, root);
		}
	}

	/* 根结点变为黑色，防止之前的操作导致根结点变为红色 */
	rb_set_black(root->rb_node);
}

代码处理显然是经过分析的，即多种情况的转化图，这种编写习惯非常值得学习

Deletion

对于红黑树来说，删除的操作可能不那么复杂，但是情况却有点多，这对于计算机来说不是难事，但是人理解起来不太简单，这也是计算机的优势了，善于无错的处理复杂情况。

删除的步骤，就是选择合适的位置（跟 BST 一样），删除之后再来调整。

上面说的很清楚拉，真心感激这个课件，省了我好多精力~

最简单的情况，删除的节点是红色节点

之前也提到了，红色节点不会影响 RB trees 的平衡，所以删除它不会有任何影响

注意，当与前继（或者后继节点）替换位置之后，考虑的颜色是替换之后的节点，原来的位置已经不再考虑范围了，下文在没有强调的时候，都是指替换之后的位置

删除的节点是黑色节点，Double Black

当删除的节点是黑色的时候，就会出现 D-B 的情况，那么思想是什么呢，就是补偿，之前我们新插入一个节点，其实思想也是，只是补偿的是另外一个子树，想办法把节点移动到另外一个子树，来减少树高差，现在补偿的就是自己所在的子树了。

所以，整个思想都是，从另外一条子树偷一个红色节点，然后转换为黑色，这样总的黑色节点就没有少，而自己的子树也多了一个结点，从而维持红黑树的“平衡“。

总结的好棒

现在我们来考虑几种情况把。

Case 1， 兄弟是黑色，它的孩子有红色

为了简化描述，删除节点之后，接替在它的节点的那个位置我们称为 Child（C），其父母我们称为 P，然后 P 的另外一个孩子 Sibling（S），它的孩子我们就成为 Nephew（N）侄子。

对于这种，右侧是一条直线的，一个左旋即可解决，但是这里给的例子是 P为黑节点，其实它不一定是黑色，往往很有可能是红色。 看我画的示意图比较清楚

加粗黑色，表示 D-B

由于菱形那一块 以及 P有可能是红色，所以旋转之后的必须要重新染色，怎么染色呢？答案是 S 变为 P 原来的颜色（即 S->color = P->color），然后 P 变为黑色，然后 S 的孩子，即 Nephew（N）变为黑色。

左子树 白色 +2*黑 右子树 白色 + 1*黑

这样无论 P 究竟是红色 还有 黑色，都可以解决两边子树的黑色节点的问题，D-B 表示俩个黑节点，最后面，它所在的那一段，也仍然是 白色（可黑可红）+ 两个黑色节点，另外一个子树也一样。菱形呢？可以看出它上层原是 白色 + 黑，现在也是，所以这个调整非常正确。

删除的难点，就在于删除之后这个重新染色，其他操作都是很自然的，值得一提的是，菱形那一块如果是红色的，其实包括了 俩个N都是红色的情况。

Case 1.2 兄弟是黑色，它的孩子是红色，但不在一条直线

接着上面的例子，也就是说，右 N 侄子 是黑色，左 N 是红色。

虽然课件上是粉色（可变），我们举的例子就是黑色

因为俩个 N 都是红色 刚才已经涉及了，现在讨论的是 P S N（Nephew）不在一条直线的情况。以课件的例子，就是， P S Z 不是在一条直线。

同理，白色是可黑可红

是否记得，我们在说插入的算法的时候，也谈到了不在一条直线的情况，解决方案就是旋转一次，转换为在一条直线的情况( Case 1 )。～

right rotate

考虑，菱形所在的那条直线，是不是少了一个黑色节点，而 S 的右孩子（即 右 N）一定是黑色，否则我们也不会来到这一步了，所以，我们直接把红色变为黑色，S 变为红色，即可保持平衡，按之前的说法就是，S 和 右 N 之间还有一个位置可以放红色节点。

如此一来，转换为了在一条直线的情况了，只是有一点值得注意，菱形一定是黑色，这里就有读者自己思考把～

Case 2 兄弟为黑色节点，侄子也全为黑色

这种情况，课件上说的很明白了，另外一侧已经没有红色节点可以拿了，只能够向上寻找，如果 P 正好是红色，那我们就不需要往上，否则 P 变为 D-B。这种情况，在实际代码编写的时候，是要先于 Case 1 判断，因为向上传递之后，可能就又是 Case 1（包括 Case 1.2 ）。

Case 3 兄弟节点为红色

这也是最后一种情况了，但也是最先要判断的，如果我的兄弟都是红色，我自然不需要看我的侄子了，我的兄弟的红色就可以拿来使用。（这里隐含着 P 一定是黑色 ，N一定是黑色）

先旋转，再重新着色，因为拿了另外一侧树的一个黑色节点，所以 现在 S 已经黑色，转换成了之前的 Cases，如果下一步发现新的 S（原来的侄子变为 S 了）的孩子都是黑色，那么只需要重新染色就好了，因为现在的 P 一定是红色。

实际的转换是 Case 3 ->{ Case 1 1.2, Case 2}，而 Case 2 -> { 直接解决， Case 1 1.2 Case 2 Case 3 }，然后 Case 1.2 -> Case 1

这给了实际编写代码的思路，流程图我就不画了，就是上面所说的过程，下面的 node 指的就是我所画的图的 Child（C），其实就是现在为 D-B 的那个节点，这个函数是找到了删除的位置，并且删除的节点是 D-B 这个函数才被调用的，只负责处理前面提到的 Cases。

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
			     struct rb_root *root)
{
	struct rb_node *other;

	while ((!node || rb_is_black(node)) && node != root->rb_node)
	{  /* Case 2 will propagate upward~ */
		if (parent->rb_left == node)
		{
			other = parent->rb_right;

			 /* sibling is red~  Case 3 */
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_left(parent, root);
				other = parent->rb_right; /* update sibling */
			}

			/* --- now sibling is black  ---*/

			/* two children are black( null included )  Case 2 */
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
				/* Case 2 will propagate upward~ */
			}
			else
			{	/* anyone of them is red～ || both are red, Case 1 */
				if (!other->rb_right || rb_is_black(other->rb_right))
				{
					/* node 是左节点，so 处理 左侄子是 红色的情况 Case 1.2，*/
					rb_set_black(other->rb_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right; /* 更新 update  */
				}

				/* 三种情况都回到了这儿~, 右侄子是红色，parent不确定，other是黑色，node也是黑色 */
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_right);
				/* parent 之所以是黑色，是为了防止，左右侄子同时都为红色的情况，这个要死记 XXX */
				__rb_rotate_left(parent, root);
				/* 至此。 other 便为局部的 根结点 */


				node = root->rb_node; /* set black */
				break;
			}
		}
		else
		{ /* 以下都是镜面操作，上面是 left 这里就是 righ ， vice versus*/
			other = parent->rb_left;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_left || rb_is_black(other->rb_left))
				{
					rb_set_black(other->rb_right);
					rb_set_red(other);
					__rb_rotate_left(other, root);
					other = parent->rb_left;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->rb_node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node); /* 传递上去的 父母节点 设置为 黑色 */
}

上面的代码是处理若干 cases 的代码，下面就是我们之前说的，BST 删除节点的步骤了，很简单。

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *child, *parent;
	int color;

	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else
	{
	/* find its successor（predecessor is also fine）*/
		struct rb_node *old = node, *left;

		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;

		if (rb_parent(old)) {
			/* 连接 node 与 删除结点的 parent */
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = node;
			else
				rb_parent(old)->rb_right = node;
		} else
			root->rb_node = node; /* 被删除的节点是根结点 */

		/* node是successor 一定没有左 child */
		child = node->rb_right;

		parent = rb_parent(node);
		/* 此处正是开始删除节点的位置（转移后），记录它的孩子和父母 */
		color = rb_color(node);

		if (parent == old) {
			/* 意味着，被删除的节点的 successor 就是其 右节点（没有左节点 ） */
			parent = node;
		} else {
			if (child)
				rb_set_parent(child, parent);
			/* 删除的不是叶子节点，连接孙子和爷爷，此处被删除节点准备被抽出 */

			/* 被抽出后， 父母的左方就是孩子应该在的位置 前提是 successor不是其右节点*/
			/*
			 *      O (parent
			 *     /                           O
			 *    O （ successor） ->          /
			 *     \                         O
			 *      O (child, maybe null )
			 *
			 */
			parent->rb_left = child;
			node->rb_right = old->rb_right; /* 此处 assignment */
			rb_set_parent(old->rb_right, node);
		}

		/* 此处，将node的位置替换到原来要删除的位置 */
		node->rb_parent_color = old->rb_parent_color;
		node->rb_left = old->rb_left;
		/* 此处的情况可能是 successor是右节点，所以不用给右赋值 */
		rb_set_parent(old->rb_left, node);

		goto color;
	}

	/* 有一个是 null，或者都为 null 的情况*/
	parent = rb_parent(node);
	color = rb_color(node);

	if (child)
		rb_set_parent(child, parent);
	if (parent)
	{
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		root->rb_node = child; /* child 作为根节点，因为没有父母 */

 color:	/* 如果删除的节点是 黑色，否则不需要处理 */
	if (color == RB_BLACK)
		__rb_erase_color(child, parent, root);
}

末

红黑树的提出以及处理方案，处处体现着“补偿”的思想，多了就从少的子树拿，少了就从多的子树拿，再不济，就交给上层处理，大部分的 R-B 处理都是 Locally，不需要惊动整棵树，所以它非常的适合处理动态性强的结构，比如进程的调度队列，进程的内存空间管理以及set，map的实现等等。

实际代码的编写使得流程图的重要性得以体现，非常棒！