红黑树插入为什么先染红从一个多出来的黑结点到变色与旋转我在旧笔记里写过一个问题插入红黑树的新结点到底应该是红色还是黑色当时记下来的理由是如果插入黑色这条路径就比别的路径多了一个黑结点插入红色则只可能出现连续的红结点。这句话可以作为入口但光背下来还不够。多一个黑结点为什么麻烦连续两个红结点又该怎么改我们拿几棵很小的树走一遍先把插入讲完删除这次不混进来。先看黑色结点到底在数什么下面用B表示黑色R表示红色。红黑树首先仍然是一棵二叉搜索树左子树的值比当前结点小右子树的值比它大。颜色是额外的约束不替代大小关系。颜色相关的规则可以先记这几条根是黑色空孩子也当作黑色的NIL红结点的孩子不能是红色从同一结点出发到各个后代NIL的路径经过的黑结点数必须相同。最开始只有一个1010(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、710(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 -stdc11 -Wall -Wextra -Werror demo.c -o demo ./demo输出为root7, left5, right10。如果只是想跟着图理解调整读到前面即可这部分用来把图和真实指针接起来。本文的两段式组织也可以对照Linux内核红黑树接口说明先按键查找位置并连接结点再调用颜色修复接口。不过上面是独立教学实现没有复制内核的结点布局或增强树接口。 
长河君 · 2026/10/24 3:38:03 · 阅读 1.2k 红黑树插入为什么先染红？从一个多出来的黑结点，到变色与旋转
红黑树插入为什么先染红从一个多出来的黑结点到变色与旋转我在旧笔记里写过一个问题插入红黑树的新结点到底应该是红色还是黑色当时记下来的理由是如果插入黑色这条路径就比别的路径多了一个黑结点插入红色则只可能出现连续的红结点。这句话可以作为入口但光背下来还不够。多一个黑结点为什么麻烦连续两个红结点又该怎么改我们拿几棵很小的树走一遍先把插入讲完删除这次不混进来。先看黑色结点到底在数什么下面用B表示黑色R表示红色。红黑树首先仍然是一棵二叉搜索树左子树的值比当前结点小右子树的值比它大。颜色是额外的约束不替代大小关系。颜色相关的规则可以先记这几条根是黑色空孩子也当作黑色的NIL红结点的孩子不能是红色从同一结点出发到各个后代NIL的路径经过的黑结点数必须相同。最开始只有一个1010(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、710(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 -stdc11 -Wall -Wextra -Werror demo.c -o demo ./demo输出为root7, left5, right10。如果只是想跟着图理解调整读到前面即可这部分用来把图和真实指针接起来。本文的两段式组织也可以对照Linux内核红黑树接口说明先按键查找位置并连接结点再调用颜色修复接口。不过上面是独立教学实现没有复制内核的结点布局或增强树接口。