企业官网建设流程全解析

红黑树插入为什么先染红？从一个多出来的黑结点，到变色与旋转

我在旧笔记里写过一个问题：插入红黑树的新结点，到底应该是红色还是黑色？

当时记下来的理由是：如果插入黑色，这条路径就比别的路径多了一个黑结点；插入红色，则只可能出现连续的红结点。

这句话可以作为入口，但光背下来还不够。多一个黑结点为什么麻烦？连续两个红结点又该怎么改？我们拿几棵很小的树走一遍，先把插入讲完，删除这次不混进来。

先看黑色结点到底在数什么

下面用B表示黑色，R表示红色。红黑树首先仍然是一棵二叉搜索树：左子树的值比当前结点小，右子树的值比它大。颜色是额外的约束，不替代大小关系。

颜色相关的规则可以先记这几条：根是黑色；空孩子也当作黑色的NIL；红结点的孩子不能是红色；从同一结点出发，到各个后代NIL的路径，经过的黑结点数必须相同。

最开始只有一个10：

10(B) / \ NIL(B) NIL(B)

从10走到左边空孩子，经过10、NIL两个黑结点；走到右边也是两个。

现在按二叉搜索树的插入办法，把5接到10左边。假如把5染黑：

10(B) / \ 5(B) NIL(B) / \ NIL NIL 左边：10(B) -> 5(B) -> NIL(B) 3个黑结点 右边：10(B) -> NIL(B) 2个黑结点

新结点替换了原来的一个空孩子，下面又接了两个空孩子。左边因此多经过一个黑色的5，右边却没增加。

如果5是红色：

10(B) / \ 5(R) NIL(B) / \ NIL NIL 左边：10(B) -> 5(R) -> NIL(B) 2个黑结点 右边：10(B) -> NIL(B) 2个黑结点

这次两边仍然一样。后面的图为省空间不再画NIL，但空孩子依然按黑色处理。

先插入红色，保住了原来的黑色结点数。如果父结点是黑色，甚至不需要再调整。只有父结点也是红色时，才出现红红相连；如果新结点就是根，最后把它染黑即可。

这里并不是说“黑色绝对不能插入”，而是这种插入算法选择先保住黑色数量，把修复的问题集中到局部。

父亲红了，先看看它的兄弟

从这棵合法的树开始，再插入1：

插入前： 10(B) / \ 5(R) 15(R) 接入1以后，暂时不合法： 10(B) / \ 5(R) 15(R) / 1(R) <- 与5连续为红色

1的父结点是5，祖父是10。父亲的兄弟15，通常称作1的“叔叔”。现在父亲和叔叔都是红色。

如果只把5改黑，走左边会多一个黑结点；所以把15也一起改黑。同时，原来黑色的10改红：

局部变色： 10(R) / \ 5(B) 15(B) / 1(R) 最后处理根：10改回黑色 10(B) / \ 5(B) 15(B) / 1(R)

为什么中间要把10改红？看经过这个局部的路径：原来经过黑色10，再走红色5或15；变色后经过红色10，再走黑色5或15。这部分仍然贡献一个黑结点。5下面经过1的路径也一样，1还是红色。

如果10上面还有父结点，就把10作为新的检查对象，看看它有没有和父亲连续为红色，不能直接停。这个例子里10已经是根，把根染黑会给所有路径同时加一个黑结点，不会让路径之间失衡。

所以“父红、叔红”的处理是变色后向上检查，不是看到红红相连就旋转。

叔叔是黑色：先看10、5、1

重新从空树开始，依次插入10、5、1。接入1后：

10(B) <- 祖父 / 5(R) <- 父亲 / 1(R) <- 新结点

叔叔是10的右孩子，这里为空，所以按黑色处理。与刚才不同，这次没法把左右两个红孩子一起染黑：右边根本没有那个红叔叔。

三个数是1 < 5 < 10。如果让中间的5来到上面，会得到一个很自然的形状：

5(B) / \ 1(R) 10(R)

大小关系没变，红红相连也没了。从5到两边空孩子，都只经过黑色5和黑色NIL。

这里做了两件事：以10为支点右旋，让5上来、10下去；再让5继承原来局部根的黑色，10改红。不能只记“旋一下”，漏掉颜色变化。

旋转到底怎样改连接？带上子树来看：

右旋前： 10 / \ 5 C / \ A T 右旋后： 5 / \ A 10 / \ T C

大小关系一直是：A里的值 < 5 < T里的值 < 10 < C里的值。

5原来的右子树T要交给10当左子树，它不能跟着5挤到10右边。代码里还要更新这些结点的父指针，以及原来指向10的那条连接；如果10本来是整棵树的根，根指针也要换成5。

这就是旋转比“交换两个数字”多出来的事情：值没有互换，连接变了。

如果插入的是7，为什么要转两次？

仍然重新开始，依次插入10、5、7：

10(B) / 5(R) \ 7(R)

这次中间的数是7，但它在5的右边。直接照搬上面的右旋，5虽然会上去，7仍然可能和红色的10连在一起，并没有修好。

先在5这里左旋，把折线变成刚才已经会处理的直线：

先对5左旋： 10(B) / 7(R) / 5(R) 再对10右旋，并调整颜色： 7(B) / \ 5(R) 10(R)

第一步不负责完成颜色修复，只负责把形状变成“左、左”；第二步才按上一节的方法，把中间值提上来并变色。

到这里不必再背四套不同故事：父亲在祖父右边时，左右镜像即可。10、15、20对应右右，10、15、12对应右左。

把刚才的判断放回C代码

插入分成两段：先按大小找到空位置，接入一个红结点；再从这个结点向上修复。下面这个循环只在父结点为红时继续：

while (is_red(z->parent)) { Node *p = z->parent; Node *g = p->parent; /* 根据p在g的左边还是右边，找叔叔并处理 */ }

为什么这里可以取祖父？修复过程中根保持黑色，或者刚刚变红的根已经成为当前的z；后一种情况z没有父亲，循环不会进入。因此真正进入循环时，红色父亲不可能是根。

父亲在左边时，处理顺序就是刚才的图：

• 叔叔为红：父亲、叔叔改黑，祖父改红，z移到祖父继续检查。
• 叔叔为黑：如果是左右折线，先对父亲左旋；再让新的父亲变黑、祖父变红，对祖父右旋。

折线旋转后，谁是父亲、谁是祖父会变，所以完整代码里会重新读取p和g。这一处不重新读，变量还指着旧角色，很容易把颜色改错。

这份实现只做整数集合的插入：重复值不新增结点，返回0；插入成功返回1；内存分配失败返回-1。没有删除接口，也不是线程安全容器。

代码跑完，怎么知道它真的还是红黑树？

只看中序输出从小到大，还不够。一个普通的、退化成链的二叉搜索树，中序同样有序；父指针接错了，也可能暂时看不出来。

所以检查程序没有照抄插入时的分类，而是递归检查结果：

• 给每个结点传入祖先约束的上下界，检查整个子树的大小关系。
• 检查孩子的父指针是否指回当前结点。
• 遇到红结点，检查左右孩子都不是红色。
• 左右子树分别返回路径上的黑结点数，两边不相等就失败。
• 另外检查根是黑色、结点总数正确，之前插入的每个值都还能查到。

每插入一个数就检查一次，而不是等全部插完才检查。相同的几个数，换个顺序就可能走不同的旋转分支，所以测试也改变插入顺序。

用前面的四组三结点例子运行，得到：

插入10、5、1： 根5(B)，左1(R)，右10(R) 插入10、5、7： 根7(B)，左5(R)，右10(R) 插入10、15、20： 根15(B)，左10(R)，右20(R) 插入10、15、12： 根12(B)，左10(R)，右15(R)

这些小输出可以直接对着前面的图看。完整测试另外枚举了1到7的全部排列，检查升序、降序、重复值和整数边界，再故意破坏颜色、大小关系或父指针，确认检查器确实会报错。

红黑树的颜色限制保证高度为O(log n)。插入先沿一条路径找位置，变色最多沿祖先向上传递，旋转只改局部连接，所以单次插入是O(log n)，不计新结点的辅助空间为O(1)。销毁树的递归函数另用O(log n)栈空间。

附：完整插入实现

下面是本文例子使用的C11源码。调用前设Node *root = NULL;，调用rb_insert(&root, key)插入，结束时用rb_destroy(root)释放。查找过程使用<和>，没有用两数相减比较，避免边界整数相减溢出。

#include <stdlib.h> typedef enum { RED, BLACK } Color; typedef struct Node { int key; Color color; struct Node *left, *right, *parent; } Node; static int is_red(const Node *n) { return n != NULL && n->color == RED; } static void rotate_left(Node **root, Node *x) { Node *y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; if (!x->parent) *root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } static void rotate_right(Node **root, Node *x) { Node *y = x->left; x->left = y->right; if (y->right) y->right->parent = x; y->parent = x->parent; if (!x->parent) *root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->right = x; x->parent = y; } static void fix_insert(Node **root, Node *z) { while (is_red(z->parent)) { Node *p = z->parent; Node *g = p->parent; if (p == g->left) { Node *u = g->right; if (is_red(u)) { p->color = BLACK; u->color = BLACK; g->color = RED; z = g; } else { if (z == p->right) { z = p; rotate_left(root, z); } p = z->parent; g = p->parent; p->color = BLACK; g->color = RED; rotate_right(root, g); } } else { Node *u = g->left; if (is_red(u)) { p->color = BLACK; u->color = BLACK; g->color = RED; z = g; } else { if (z == p->left) { z = p; rotate_right(root, z); } p = z->parent; g = p->parent; p->color = BLACK; g->color = RED; rotate_left(root, g); } } } (*root)->color = BLACK; } /* 1: inserted; 0: duplicate; -1: allocation failed. root must be non-NULL. */ int rb_insert(Node **root, int key) { Node *parent = NULL; Node **link = root; while (*link) { parent = *link; if (key < parent->key) link = &parent->left; else if (key > parent->key) link = &parent->right; else return 0; } Node *z = malloc(sizeof *z); if (!z) return -1; *z = (Node){ .key = key, .color = RED, .parent = parent }; *link = z; fix_insert(root, z); return 1; } void rb_destroy(Node *root) { if (!root) return; rb_destroy(root->left); rb_destroy(root->right); free(root); }

把上面的实现保存为rb_insert.c，下面的演示文件与它放在同一目录：

#include <stdio.h> #include "rb_insert.c" int main(void) { Node *root = NULL; int keys[] = {10, 5, 7}; for (int i = 0; i < 3; ++i) { if (rb_insert(&root, keys[i]) != 1) { rb_destroy(root); return 1; } } printf("root=%d, left=%d, right=%d\n", root->key, root->left->key, root->right->key); rb_destroy(root); return 0; }

例如用GCC编译demo.c，再运行产物：

gcc -std=c11 -Wall -Wextra -Werror demo.c -o demo ./demo

输出为root=7, left=5, right=10。如果只是想跟着图理解调整，读到前面即可；这部分用来把图和真实指针接起来。

本文的两段式组织也可以对照Linux内核红黑树接口说明：先按键查找位置并连接结点，再调用颜色修复接口。不过上面是独立教学实现，没有复制内核的结点布局或增强树接口。