红黑树的插入

红黑树插入的结点，必须先标记为红色。 因为插入红结点不会改变一条路径上黑结点的数量，也就不会影响树高。

但插入红结点会违背 《一条路径上不能有连续的两个红结点》 这一原则。这样的情况比较常见，所以可以将插入的红结点分为以下五种场景，各种特殊情况最终都能转换成合理的红黑树。

?

场景一：插入根结点。

这种是最简单的情况了，直接把根结点变成黑色即可，内核源码中也是一笔带过。

源码链接：v6.0.15/source/lib/rbtree.c

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	// ...
	while (true) {
		// 如果插入的节点是根节点
		if (unlikely(!parent)) {
			rb_set_parent_color(node, NULL, RB_BLACK);
			break;
		}
        // ...
	}
}

?

场景二：父结点是黑色。

这种局面，新插入的红结点并没有打破红黑树的规则，所以不需要做任何调整。

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	// ...
	while (true) {
		// 如果父节点是黑色
		if(rb_is_black(parent))
			break;
        // ...
	}
}

如图，新插入的100，400的父节点是黑色，不需要做任何调整。

?

---

?

场景三：父结点和叔结点都是红色。

简单来说，这种情况，只要将父结点、叔结点变黑，爷结点变红就行了。

但是细心的朋友可能会发现，如果爷结点的父亲是红色，那不又出现了两个连续的红结点了吗？

没错，场景三处理完后，并不一定插入完成，有可能会进入接下来的场景四中。但这个时候，需要把当前节点给换一换啦，不再是把C当成新插入的结点，而是把G当成新结点插入到红黑树中，继续进行场景处理。 你看，源码中就是这样的逻辑：

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

	while (true) {
		/*
		 * Loop invariant: node is red.
		 * 如果当前结点还是红色，那就一直循环
		 */

		// ...
		gparent = rb_red_parent(parent);

		tmp = gparent->rb_right;
		if (parent != tmp) {	/* parent == gparent->rb_left */
			if (tmp && rb_is_red(tmp)) {
				// ...
			}

			tmp = parent->rb_right;
			if (node == tmp) {
				// ...
				tmp = node->rb_right;
			}

			// 各种场景处理完后，会变更当前结点的指向，直到符合红黑树规范。
			WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
			WRITE_ONCE(parent->rb_right, gparent);
		} else {
			// ...
		}
	}
}

看看下面这个例子：

当新结点10插入到树中后，导致其爷结点50变成了红色。当场景三处理完后，又继续对连续的两个红结点50、100又进行了其它场景处理，直到红黑树符合规范为止。

?

---

?

场景四：父结点是红色，叔结点是黑色或者不存在，且爷、父、新节点不在同一斜边上。

其实场景四有两种镜像：

1. 父结点是红色，叔结点是黑色或者不存在，父结点是爷结点的左孩子，新结点是父结点的右孩子。
2. 父结点是红色，叔结点是黑色或者不存在，父结点是爷结点的右孩子，新结点是父结点的左孩子。

如图：

给人的感觉就像是两条腿走成了内八字的感觉，所以处理方法就是，使其通过旋转变成外八字，也就是场景五。

怎样进行旋转，前面有文章进行阐述，这里就不再啰嗦了。上图镜像1是对P结点进行左旋，镜像2是对P结点进行右旋。

场景四就不方便展示动画了，因为它只是一种中间过渡形态，最终都会转变成场景五。

?

---

?

场景五：父结点是红色，叔结点是黑色或者不存在，且爷、父、新节点在同一斜边上。

没是，就是场景四引申而来的外八字，它也有两种形态：

1. 父结点是红色，叔结点是黑色或者不存在，父结点是爷结点的左孩子，新结点是父结点的左孩子。
2. 父结点是红色，叔结点是黑色或者不存在，父结点是爷结点的右孩子，新结点是父结点的右孩子。

如图：

针对这样的场景，需要先对爷结点G进行左旋或右旋，再将父结点、爷结点变色，总共分成两步：

是不是感叹前人的智慧有多么神奇？来，我们看一个动画，一个将场景四、场景五衔接起来的过程：

插入结点30后，先对25结点进行左旋，使25结点成为30结点的右孩子，一个外八字。这就完成了场景四往场景五的过渡。紧接着，由于25、30都是两个连续的红结点，并且与50结点在同一斜边上。先对50进行右旋，使30成为新的父结点。再进行变色，30由红变黑，50由黑变红，完成了最终的调整。

?

---

?

总结

当你熟悉了上面五种场景后，无论红黑树已经有多大，无论新节点从哪个位置插入，都能按合适的方式调整整个树的高度，就才是插入算法的精妙所在！