【数据结构】红黑树的 C 代码实现——包括插入和删除操作的详细解析
文章目录
推荐一个零声教育学习教程，个人觉得老师讲得不错，分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，点击立即学习: https://github.com/0voice 链接。
随处可见的红黑树
红黑树是我们生活中最为常见的数据结构，常见到什么程度？常见到我们的数据库、我们的文件系统目录条为了实现快速的文件调用而使用了他们。文件为何可根据某项有序指标自动排列（而且还可以供用户选择），原因就是在于他们使用了红黑树去组织数据，而红黑树排布数据的依据是 有序的键 ，只要是有序的事物都可以使用红黑树去组织。比方说文件的日期、比方说文件的大小，比方说文件名所对应的 ASCII 条码的大小…不过这都不是最重要，最重要的是文件数据的调用速度快。
我们 Windows 的文件夹
我们访问网页时，所罗列的各种数据，比如零声教育的网站
如果你问 ”为什么不使用链表呢？“ 首先链表的顺序是根据插入的顺序来定的，它的排序依据很单一，其次他的搜索效率很低，时间复杂度是 O ( N ) O(N) O(N) ，我们总不能为了调用一个目录项，就重头检查到尾吧？正确的做法应该是使用红黑树去组织键值有序的文件，然后调用他们，实现时间复杂度为 O ( l o g N ) O(log N) O(logN) 的搜素。
红黑树的存储性能好于链表，但是链表也是有有点的，那就是极度强调 ”程序正义性“、”程序性流程“ 他可不管花里胡哨的依据，他只根据 先来后到 来组织数据。比如 C 语言的程序 线程栈 可以实现递归调用、for 和 while 循环。再比如，线程池设计的 任务队列，任务先排队的，先会得到线程的受理。
红黑树的基础
一、红黑树的定义
红黑树的定义有五条
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（空节点或NIL节点）是黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
- 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点。
注解：1、根节点就只有一个。2、叶子节点是拟制的虚拟节点（叶子节点不是真正意义上的节点），叶子结点就只有一个，即树底端的节点所有子节点都是指向同一个叶子结点，并且他是黑色的，但不计算入黑高之中。3、根节点的父节点是叶子结点，叶子结点没有子节点（在代码中的设计），因而我们才说叶子结点是虚拟的。
大家可以看一下下面四棵树，判断一下哪个是红黑树。
答案是仅右上方的第二棵树是红黑树。因为第 1、3 棵树的黑高不统一，第 4 棵树出现了连红现象。
二、红黑树是一个搜索算法
我们注意到上图的红黑树的节点都是有数值，这些数值就是红黑树的键——key，它们是搜索的依据。红黑树是对键值对型（key-value）的数据进行空间排布的算法，经过排布后的数据节点群会有极高的搜索效率。
搜索的过程其实就是 key 的数值比大小的过程。从根节点出发，搜查点比当前节点的 key 值大则往右走，key 值小则往左走，直至深入到红黑树最底层，有就有没有就没有，没有就说搜不到。
三、红黑树的自平衡性与时间复杂度
红黑树的节点分成红节点与黑节点。为什么要两种颜色，而不只用一种呢？按照定义一棵树全是黑节点也是 OK 的。为什么非要引入红色节点呢？
- 红黑树的根本设计就是树的双色的冲突，当一颗双色树满足红黑树的定义它一定会是平衡的。
- 在代码的实现之中，我们每次插入的节点都是红色的，而后在根据当前的情况去调节树的物理结构。代码的设计上就是时刻引入红色，制造冲突，时刻调整树的结构。
我们要详细解析红黑树的第 4 条定义的作用。下面的这棵树就不是平衡的，因此他不是红黑树，我们以 R 代表 红色，B 代表黑色。这棵树满足定义的第五条——”黑高平衡“，但违反了第 4 条的 ”不可连红“。实际上，只要我们把这树修改一下，让其满足红黑树的定义，他会重新变平衡的。
B
/ \
R B
/ \
R B
/ \
R B
/ \
B B
/ \
R R
双色冲突的目的就是制造矛盾，时刻对不平衡现象发出警报，克制住树的某一段疯长，最好的情况是平衡发展。因为一棵树的若能平衡发展，那无疑是有极高的搜索效率的的，我们且看下面这颗平衡的树。这棵树共有 15 个节点，我们从根节点出发，搜索任意一个节点，都不超过 4 步。换句话说红黑树的组织方式可以对节点总数进行对数降阶，拥有极高的搜索效率。（提示，所有节点都是有键值的，即 H 最小，O 最大，H< D <I < B < J < E < K < A < L <F <M < C < N <G <O ，我们是从根节点 A 出发，逐层的比对键的大小，小于则往左走，大于则往右走）。
A
/ \
B C
/\ / \
D E F G
/ \ / \ /\ /\
H I J K L M N O
上面这棵树搜素的平均时间复杂度是（搜索步骤最多的是最后一行，共四步，最少的是第一行，只有一步）
1 15 ∑ k = 1 4 k ⋅ 2 k − 1 = 3.27 < 4. \frac{1}{15}\sum_{k=1}^{4} k \cdot 2^{k-1} = 3.27 < 4. 151k=1∑4k⋅2k−1=3.27<4.
我们采用数学归纳法，一棵完全平衡的红黑树的平均搜索时间复杂度是
1
N
∑
k
=
1
log
2
(
N
+
1
)
k
⋅
2
k
−
1
\frac{1}{N}\sum_{k=1}^{\log_2 (N+1)} k \cdot 2^{k-1}
N1k=1∑log2(N+1)k⋅2k−1
当 N 趋于无穷大，这是一个无穷级数，且难以计算，但是求和号内部的函数 k ⋅ 2 k − 1 k \cdot 2^{k-1} k⋅2k−1 是单调的，利用 《数学分析》中的 ”积分判别法“ 的思路，，上述的级数的发散收敛性等于以下的反常无穷积分，而且无穷大的阶次是一样的，两者的比值也刚好是 1.
∫
1
log
2
(
N
+
1
)
x
⋅
2
x
−
1
d
x
=
1
2
ln
2
log
2
(
N
+
1
)
+
O
(
1
)
.
\int_1^{\log_2 (N+1)}x\cdot2^{x-1} dx =\frac{1}{2\ln 2} \log_2 (N+1) + O(1).
∫1log2(N+1)x⋅2x−1dx=2ln21log2(N+1)+O(1).
只能说这个算法、数据结构非常厉害，时间复杂度在
O
(
log
2
N
)
O(\log_2 N)
O(log2N)。
红黑树的左旋与右旋
左旋与右旋是调整红黑树结构的方法，红黑树的左旋与右旋都是针对 ”顶点“ 来进行的。具体内容可见如下。
左旋的图示：读者可观察一下，左旋是沿着 ”金字塔顶点“ 进行左旋，”金字塔内侧“ 的分支会指向原顶点，顶点被更新为原顶点的右子节点，而原来的顶点则会被降级，变成新顶点的左子节点。
左旋是对顶点进行的
————————————————————————————————————————————————————
A
\ 对 A 可以左旋（对 B 不可以左旋）
B
变成
B
/
A
————————————————————————————————————————————————
A
/ \
C B 可以对 A、B、C 进行左旋
/ \ / \
D E F G (这一行下方任意)
示例一：对 A 左旋
B
/ \
A G
/ \ (有趣的是，BCGF 为黑色，其余为红色，整棵树也是平衡的)
C F
/ \
D E
示例二：对 B 左旋
A
/ \
C G
/ \ /
D E B
/
F
示例三：对 C 左旋
A
/ \
E B
/ / \
C F G
/
D
右旋也是类似的：读者可观察一下，右旋是沿着 ”金字塔顶点“ 进行右旋，”金字塔内侧“ 的分支会指向原顶点，顶点被更新为原顶点的左子节点，而原来的顶点则会被降级，变成新顶点的右子节点。
右旋是对顶点进行的
——————————————————————————————————————————————————————
A
/ 对 A 可以右旋（对 B 不可以左旋）
B
变成
B
\
A
————————————————————————————————————————————————————————————————
A
/ \
C B 可以对 A、B、C 进行右旋
/ \ / \
D E F G (这一行下方任意)
示例一：对 A 右旋
C
/ \
D A
/ \ (有趣的是，BCDE 为黑色，其余为红色，整棵树也是平衡的)
E B
/ \
F G
示例二：对 B 右旋
A
/ \
C F
/ \ \
D E B
\
G
示例三：对 C 有旋
A
/ \
D B
\ / \
C F G
\
E
红黑树如何插入一个节点————递归修改颜色
零声教育的 King 老师给出了一个相当精妙的心法——一个红黑树在插入新节点之前就已经是一个红黑树了。我们每次插入一个红色节点，是为了不断地给红黑树带来不安定的不平衡的因素，迫使其不断的自平衡。如果我们现在去套用 KING 老师的那套心法，那么会出现以下情况：
- 所插入节点的父节点是一个黑节点，红黑树的定义依旧满足成立，我们什么都不用做。
- 所插入节点的父节点是一个红节点，红黑树的定义就不再满足了，虽然黑高平衡还在，但是出现了 ”连红点“ 的情况，故而需要调整节点。
需要调节的情况继续细分（父节点是爷节点的左子节点，对称情况就此略去）：我把所插入节点的父节点记为 P，如果情况明确的话可以的标记其颜色 (B 或 R)，其处于旁系的叔节点记为 Y ，使用递归思维处理法去推广情况
第一种情况：叔节点存在
B
/ \
P_R Y_R
/ \
(+R) (+R) Z 的插入点
步骤：1、P 和 Y 染成黑色；2、Z 的记为爷爷辈节点
经过处理后，实行递归向上处理，处理上类似插入一个新的红色节点
R --> 被更新为新的 ”插入点“，递归向上处理，被识别为插入一个新的红点
/ \
P_B Y_B
/ \
(+R) (+R) Z 的插入点
推广情况：能囊括上面一个情况，Z 是抽象化广义化的插入点
所使用的处理方法和上面一样
B
/ \
P_R Y_R
/ \ /\
Z_R (N 层) (N 层)
/\
(N 层)
经过处理后
R --> 被更新为新的 ”插入点“，递归向上处理，被识别为插入一个新的红点
/ \
P_B Y_B
/ \ /\
Z_R (N 层) (N 层)
/\
(N 层)
————————————————————————————————————————————————————————————————————————
____________________________________________________________________
第二种情况：叔节点为黑色的（只能是叶子了），而且所插入的节点位于其父节点的左侧
B
/ \
P_R 叶
/
(+R)
步骤：1、爷节点右旋；2、P 点染黑
经过处理后，便可退出循环，应为情况已经处理好了
P_B
/ \
(+R) R
推广情况：能囊括上面一个情况，Z 是抽象化广义化的插入点
所使用的处理方法和上面一样
B
/ \
P_R (N 层)
/ \
Z_R (N 层)
/\
(N 层)
经过处理后，解决了
P_B
/ \
Z_R R
/\ / \
(N 层) (N 层)(N 层)
——————————————————————————————————————————————————————————————————
——————————————————————————————————————————————————————————————————
第三种情况：叔节点为黑色的（只能是叶子了），而且所插入的节点位于其父节点的右侧
B
/ \
P_R 叶
\
(+R)
步骤：1、P 点右旋；2、参考第二种情况
经过处理后，直接调用第二种情况的应对方法即可
P_B
/ \
(+R) R
推广情况：能囊括上面一个情况，Z 是抽象化广义化的插入点
B
/ \
P_R (N 层)
/ \
(N 层) Z_R
/\
(N 层)
经过处理后，再参考第二种情况
B
/ \
P_R (N 层)
/ \
Z_R (N 层)
/\
(N 层)
红黑树如何删除一个节点——用递归向上的思维处理双黑问题
在我写这篇文章之前，我参考过这位老哥的 CSDN 文章 （原文链接 在此），这个老哥讲的巨详细并且图片做的好看，但是没有给出其 C 代码。我在他的基础之上，再把删除节点的情况重新捋一捋，把情况给展开来。
我还是搬出 一个红黑树在删除新节点之前就已经是一个红黑树了 的心法，我们所删除的节点总共分成两类：
- 具有两个子节点
- 不具有两个子节点：具有单子节点或者无子节点
对于第一种情况，我们采用后继点的思维去处理，后继点的意思是 key 的数值排序上本点的顺位下一个点。我们给出一个例子。（我们需要明确的是红黑树只能组织有序的键值对型数据。）A 的后继点是 L，B 点的后继点是 J，读者只需要从红黑树的搜索算法处理解就OK。获取一个后继点的方法是，走到本点的右子点处，然后不断访问其左子节点，直到最后不能再访问，那个点就是后继点。我们真正要删的正是那个后继点，不过在此之前，为了保存数据，还是先得让后继点与之前想要删除的那个点交换内容。有趣的是，后继点一定是没有两个子节点的。故而第一种情况被归纳成了第二种情况。（其实，只要你愿意，采用前驱点的方法也是可行的。）
A
/ \
B C
/\ / \
D E F G
/ \ / \ /\ /\
H I J K L M N O
套用 一个红黑树在删除新节点之前就已经是一个红黑树了 ，于是处理的大体思路便可给出
// 1、删除最底层（无子节点）的红色节点不改变红黑树的结构 （黑色需要重新染色）
// 2、删除具有单个子节点的红色节点也不影响红黑树的结构 （黑色需要重新染色）
// 3、不能直接删除具有双子节点的节点，否则会破化物理结构，红黑树本身是有序的数据结构，后继点就是排序上刚好比要删除的点往后一位的点，他一定是不拥有双子节点，可以转而回到前两种情况
// 4、我们删除后继节点的物理结构，把其键值对内容迁移到原来想要删除的那个点上。至于原来想要删除的那个点的内容随着后继点一同被抹去。
由于情况已被归纳成所删除点都是无双子节点的情况（叶子结点不算成节点），故而我只需罗列所删节点没有两个子节点的情况及其处理方法（所删点是父节点的左子节点，对称情况忽略）。请读者耐心看，我是从一个很朴素的初学者出发，从想要一次过解决所有的情况一步一步的走到要循环把问题给上传到更高层去解决————这也是双黑问题的具体解决思路。这个理解的过程我花费了约 6 天，思考强度很大的。
首先给出的是 所删节点为黑色 而且 具有单个子节点 的情况（叶子节点不算真正意义上的节点），这种情况是相当之简单的。
只有当 Y 是黑色点时，才需要特殊处理。删掉红色是不会改变黑高的。
我们此刻可以把 Y 当作还没被删除，令 w 是兄弟节点，P 是父节点，x 是 y 的子点。其中，P 的颜色未知。
由此做情况归纳（我们只给出被删点 y 是其父 P 的左子点情况，对称的情况略去）。后继点方法，都能归纳成以下的情况（对称情况略去，都是类似的）
Y 点拥有单子节点，总共 4 种情况：删掉 Y 后，把 X 染黑即可。
P
/ \
Y_B W_B
/ |\
X_R (红点或叶子可以任意组合)
P
/ \
Y_B W_B
\ |\
X_R (红点或叶子可以任意组合)
P
/ \
Y_B W_R
\ / \
X_R B B
/| |\
(红点或叶子可以任意组合)
P
/ \
Y_B W_R
/ / \
X_R B B
/| |\
(红点或叶子可以任意组合)
这 4 种情况的最终处理结果：
P
/ \
X_B W_B
/ \
(红点或叶子可以任意组合)
P
/ \
X_B W_R
/ \
B B
/| |\
(红点或叶子可以任意组合)
紧接着给出的是 所删节点为黑色 而且 不具有单个子节点 的情况（叶子节点不算真正意义上的节点），这种情况是相当之困难的，我主要也是被这个问题难住了。我会先把所有情况罗列出来，详细说明为何需要采用递归向上去解决问题，以及 ”双黑问题“ 的本质就是让本节点以下的后代局部平衡，但整体的黑高相比旁系少了一层，并且让祖先节点染黑变身”双黑点“去参与更高层次的新的染色均衡。一旦采用递归向上解决问题，就意味着
- 推广删除底层端点的情况
- 尽可能的精简情况。
Y 点不拥有子节点，总共 11 种情况：相当之困难，归纳成四大类
一类：W 为黑点，没有真正意义上的子节点，全是叶子
P
/ \ 方案一，步骤：1、把 P 染黑，W 染红。2、把 Y 转移到 P 点上。进入下一个循环
Y_B W_B (下面全是叶结点) (此刻还没解决好，需要递归执行或者 while 循环跳到前面几种情况判断处理：1、P 点是黑点需要递归执行；2、P 点是红点则可以结束了)
二类：W 为黑点，拥有子节点
P
/ \ 方案二，步骤：1、P 点左旋。2、W 染成 P 点的颜色。3、P 点和 W 的右子节点染成黑色。
Y_B W_B
/ \
R R (下面全是叶结点)
P
/ \ (方法同第二种情况)
Y_B W_B 执行方案二。
\
R (下面全是叶结点)
P
/ \
Y_B W_B 步骤：1、对 W 点进行右旋。2、执行方案二。
/
R (下面全是叶结点)
三类：W 为红点，其左子节点没有真正意义上的子节点
P(B)
/ \ 方案三，步骤：1、P 点左旋两次。2、P 点染红色。3、W 点染黑。
Y_B W_R
/ \
B B
|\
(红点或叶子可以任意组合)
四类：W 为红点，其左子节点有子节点
P(B)
/ \ 方案四，步骤：1、W 作右旋。2、W 的左子节点染成黑色。3、P 点作左旋
Y_B W_R
/ \
B B
/ \ \
R R R
P(B)
/ \ 执行方案四。
Y_B W_R
/ \
B B
/ \ /
R R R
P(B)
/ \ 执行方案四。
Y_B W_R
/ \
B B
/ \ / \
R R R R
P(B)
/ \ 执行方案四。
Y_B W_R
/ \
B B
/ \
R R
P(B)
/ \ 执行方案四。
Y_B W_R
/ \
B B
\ | \
R (红点或叶子可以任意组合)
四类（一）：W 为红点，其左子节点有子节点，而且其左子节点也仅拥有左子节点，没有右子节点。
P(B)
/ \ 步骤：1、W 点的左子节点作右旋。2、W 的左子节点染成黑色。3、执行方案四。
Y_B W_R
/ \
B B
/ |\
R (红点或叶子可以任意组合)
-------------------------------------------------------------------
这 11 种情况的最终处理结果：
P
/ \
P(B) B (可以终结了) 这是执行了方案二的类似情形
\
(叶子，或者R)
B
/ \
B B (可以终结了) 这就是指代方案三
/ / \
P_R (红点或叶子可以任意组合)
B
/ \
P_B W_R (可以终结了) 方案四
\ / \
R B B
/ \
(红点或叶子可以任意组合)
B
/ \
P_B W_R (可以终结了) 方案四
/ \
B B
/ \
(红点或叶子可以任意组合)
P_B
\ 方案一，体现双黑（-1）的等价思想。
R
——————————————————————————————————————————————————————————————————————————————
————————————————————————————————————————————————————————————————————————————————
但是以上分析全都特别复杂，虽然情况分析全了。但是急于求成，妄图在 1、2 次循环中解决，特别是方案一，它是不充分的，方案一进入下一个循环，使用现有的哪一个分支都不可行。
--------------------------------------------------------------------------------------------------------------------------------
但是以上分析全都特别复杂，虽然情况分析全了。但是急于求成，妄图在 1、2 次循环中解决，特别是方案一，它是不充分的，方案一进入下一个循环，使用现有的哪一个分支都不可行。
新的解决方案是，就算有些情况可以一次过解决，我都必须拖延到下一个循环中解决，以最大程度的使代码可复用度提高。
（只针对上面 11 种情况，并且 Y 已经被拔除了）！！！！！！！！！！！！！！！！！！！
第一次归结双黑问题的方法
P
/ \ p1--> 步骤：1、把 W 染红；2、P 点染黑；3、X 的记号迁移到 P 点。进入下一个循环
叶_x W_B
P
/ \ p2--> 步骤：1、W 的右子节染黑，W 染成 P 点的颜色；2、P 点左旋，P 点变黑；3、把 X 的记号转移到 W 上。进入下一个循环
叶_x W_B
/ \
(R) R
P
/ \ p3--> 步骤：1、W 进行右旋，W 染红；2、此刻 W 的父节点染黑，把 W 的记号转移到 W 的父节点。3、套用 p2 方法
叶_x W_B
/
R
P_B (不能连红)
/ \ p4--> 步骤：1、W 染成黑色；2、P 点左旋；3、把 W 的记号转移到当前 X 的兄弟节点上 。进入下一个循环，X 并没有更新
叶_x W_R （这并没有把双黑问题上传，而是平级传动，转到前三种情况上）
/ \
B B
/| |\
(红点或叶点的组合)
进入下一个循环的注意事项：
1、在下一个循环之中，如果 X 是红色点就终止，因为双黑的 -1 得到宣泄
2、双黑问题向上传递后，X 不再处于底层的叶子点上。
3、P 之下的黑高为 N>=2，不计算黑叶子的话，N =1 即为以上的 4 种情况
P
/ \ 情况描述：1、W 是黑色的；2、W 的两个子节点都是黑色的。
X_B W_B 完全可以套用 p1，把双黑问题向上传递。而且情况的描述，也跟 p1 的重叠。
/\ / \
(N-1层黑) B B p1--> 步骤：1、把 W 染红；2、P 点染黑；3、X 的记号迁移到 P 点。进入下一个循环
/| |\
(N-1层黑) (N-1层黑)
P
/ \ 情况描述：1、W 是黑色的；2、W 的右子节点都是红色的。3、W 的左子节点的颜色任意。
X_B W_B 完全可以套用 p2，把双黑问题向上传递。而且情况的描述，也跟 p2 的重叠。
/\ / \
(N-1层黑) B/R R p2--> 步骤：1、W 的右子节染黑，W 染成 P 点的颜色；2、P 点左旋，P 点变黑；3、此时已经平衡了，可以跳出循环了。
/| |\
(N-1/N层黑) (N层黑)
P
/ \ 情况描述：1、W 是黑色的；2、W 的左子节点都是红色的。3、W 的右子节点的颜色是黑色的。
X_B W_B 完全可以套用 p3，把双黑问题向上传递。而且情况的描述，也跟 p3 的重叠。
/\ / \
(N-1层黑) R B p3--> 步骤：1、W 的左子节点染成黑色，W 自身染红；2、W 点右旋，把 W 的记号转移到 W 的父节点。3、套用 p2 方法
/ \ |\
B B (N-1层黑)
/| |\
(N-1层黑) (N-1层黑)
P(B)
/ \ 情况描述：1、W 是红色的；2、W 的两个子节点都是黑色的
X_B W_R 完全可以套用 p4，把双黑问题向上传递。而且情况的描述，也跟 p4 的重叠。
/\ / \
(N-1层黑) B B p4--> 步骤：1、W 染成黑色；2、P 点左旋，并且染成红色；3、把 W 的记号转移到当前 X 的兄弟节点上 。进入下一个循环，X 并没有更新
/| |\
(N层黑) (N层黑)
红黑树的数据结构 C 代码实现
我们需要明确的一点是
数据结构
=
数据定义
+
数据的操作方法。
数据结构 = 数据定义 + 数据的操作方法。
数据结构=数据定义+数据的操作方法。
所谓的数据定义：就是定义红黑树的类型
所谓的数据操作方法就是：1、左旋与右旋；2、插入操作；3、删除操作
定义红黑树数据
红黑树需要两个类型来定义，一个是红黑树节点，另一个是红黑树的根节点和叶子节点（都是唯一定义的）。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define RED 1
#define BLACK 2
typedef int KEY_TYPE;
typedef struct _rbtree_node {
unsigned char color;
struct _rbtree_node *right;
struct _rbtree_node *left;
struct _rbtree_node *parent;
KEY_TYPE key;
void *value;
} rbtree_node;
// nil 是一个拟制的虚无节点，一般都是父节点为 NULL，左右子节点都是自己，key，value 随便设置 0，但是所有叶节点的统一定义口径
typedef struct _rbtree {
rbtree_node *root;
rbtree_node *nil;
} rbtree;
实现红黑树的左旋与右旋
这是左旋，具体的思路可返回去看前面
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
/* 对于该函数来说，初始化情形只会在第三次插入节点的时候首次调用 rbtree_insert_fixup 时有可能遇到的以下情况（不一定会有初始情况）
叶
|
X_根
\
R
\
(+R)
*/
rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right
x->right = y->left; //1 1
if (y->left != T->nil) { //1 2
y->left->parent = x;
}
y->parent = x->parent; //1 3
if (x->parent == T->nil) { //1 4
T->root = y; // 这是初始化的情形
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; //1 5
x->parent = y; //1 6
}
这是右旋，具体的思路可返回去看前面
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
/* 对于该函数来说，初始化情形只会在第三次插入节点的时候首次调用 rbtree_insert_fixup 时有可能遇到的以下情况（不一定会有初始情况）
叶
|
Y_根
/
R
/
(+R)
*/
rbtree_node *x = y->left;
y->left = x->right;
if (x->right != T->nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == T->nil) {
T->root = x; // 这是初始化的情形
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
实现红黑树的插入操作
插入操作，需要先把先把节点加入红黑树，然后视情况修复红黑树（实现自平衡）。故而需要定义两个函数。
第一个是插入红黑树节点的函数，通过键 key 的数值去找到红黑底层中最合适插入的点，进行连接。
void rbtree_insert(rbtree *T, rbtree_node *z) {
rbtree_node *y = T->nil;
rbtree_node *x = T->root;
while (x != T->nil) {
y = x;
if (z->key < x->key) {
x = x->left;
} else if (z->key > x->key) {
x = x->right;
} else { //Exist
return ;
}
}
// 这里是用于实现查找合适的插入点
z->parent = y; // 这说明了，根节点的父节点是有可能会被设定为拟制的叶子结点
// 修复：确保插入后父指针正确
if (y == T->nil) {
T->root = z;
z->parent = T->nil; // 明确设置根节点的父节点
} else if (z->key < y->key) {
y->left = z;
z->parent = y; // 设置父指针
} else if (z->key > y->key) {
y->right = z;
z->parent = y; // 设置父指针
} else {
//printf("the key has been existed when insert\n");
return;
}
z->left = T->nil;
z->right = T->nil;
z->color = RED;
// 对于该函数来说，初始化情形指代整棵树首次出现连红现象（将会在第 3 或 4 次插入的时候首次调用该函数），破坏了红黑树的结构，首次使用该函数修复结构
rbtree_insert_fixup(T, z);
}
第二个是在插入操作后对红黑树的修复
// 在计算红黑树的时候，不要遗漏了叶子结点，否则会算错
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
// 一棵红黑树在插入一个新节点之前就已经是一个红黑树，如果新插入的节点的父节点是一个黑点，那么我们将不用做任何的调整
// 如果所插入点的父节点是一个红点，那么其父节点就需要调节成黑色，但这一来就会破坏黑高平衡了，本支系的黑高加 1
/* 首次进入 while 循环的时候就是首次出现连红现象（将会在第 3 或 4 次插入的时候首次调用该函数），破坏了红黑树的结构，首次使用该函数修复结构
叶
|
根
/ \
R R
/ \ / \
(+R)(+R) (+R) (+R) Z 的四种可能的插入情况
叶
|
根
/ \
R 叶 （忽略对称情况）
/ \
(+R) (+R) Z 的两种可能的插入情况
*/
/* 第一种情况：
B
/ \
P_R Y_R
/ \
(+R) (+R) Z 的插入点
经过处理后（仅需调颜色），实行递归向上处理，处理上类似插入一个新的红色节点
R
/ \
P_B Y_B
/ \
(+R) (+R) Z 的插入点
第二种情况是
B
/ \
P_R 叶
/
(+R)
经过处理后，便可退出循环，应为情况已经处理好了
P_B
/ \
(+R) R
第三种情况是
B
/ \
P_R 叶
\
(+R)
经过处理后，直接调用第二种情况的应对方法即可
B
/ \
P_R 叶
/
(+R)
*/
while (z->parent->color == RED) { //z ---> RED ，根节点自动结束循环
if (z->parent == z->parent->parent->left) {
rbtree_node *y = z->parent->parent->right; // y 允许为虚拟叶节点，叔节点
if (y->color == RED) { // y 不是叶节点
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
// 将 z 节点更新为其自身的爷爷节点，局部已经平衡了，在下一个循环之中再更新（有点递归的意思）
z = z->parent->parent; // 递归向上处理
if (z->parent == T->nil) { // 更新根节点
T->root = z;
}
} else { // y 是叶节点或黑点
if (z == z->parent->right) {
z = z->parent;
rbtree_left_rotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_right_rotate(T, z->parent->parent);
// 实际上已经平衡了，下次再往这个地方插入的时候，就会返回上一种情况去处理
if (z->parent->parent == T->nil) { // 更新根节点
T->root = z->parent;
}
}
} else {
rbtree_node *y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //z --> RED
if (z->parent == T->nil) { // 更新根节点
T->root = z;
}
} else {
if (z == z->parent->left) {
z = z->parent;
rbtree_right_rotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_left_rotate(T, z->parent->parent);
if (z->parent->parent == T->nil) { // 更新根节点
T->root = z->parent;
}
}
}
}
T->root->color = BLACK;
}
实现红黑树的删除操作
我们之前说过我们需要采用后继点的方法，删除具有双子节点的节点可以归结成删除无子节点的情况。
寻找后继点的方法。
// 这个函数是获取节点 x 所对应的左斜直线上的最小后辈字节，根节点的最小后辈节点就是全局最小后辈节点
rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
while (x->left != T->nil) {
x = x->left;
}
return x;
}
// 查找后继节点———— x 的右子树对应的左斜直线上最小后辈节点（其键 KEY 刚好比 x 的大一点），或者 x 的最大左祖先（反过来说 x 是此祖先点的最大右后辈）。
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
rbtree_node *y = x->parent;
if (x->right != T->nil) { // x 的右子节点不是叶节点
return rbtree_mini(T, x->right);
}
while ((y != T->nil) && (x == y->right)) {
x = y;
y = y->parent;
}
return y;
}
然后定义删除子节点的函数
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {
// 原理很简单：红黑树在删除一个节点之前本身是一个红黑树。
// 1、删除最底层（无子节点）的红色节点不改变红黑树的结构 （黑色需要重新染色）
// 2、删除具有单个子节点的红色节点也不影响红黑树的结构 （黑色需要重新染色）
// 3、不能直接删除具有双子节点的节点，否则会破化物理结构，红黑树本身是有序的数据结构，后继点就是排序上刚好比要删除的点往后一位的点，他一定是不拥有双子节点，可以转而回到前两种情况
// 4、我们删除后继节点的物理结构，把其键值对内容迁移到原来想要删除的那个点上。至于原来想要删除的那个点的内容随着后继点一同被抹去。
// 初始化
rbtree_node *y = T->nil; // y 将会是后继节点或者直接的想要删除的那个点
rbtree_node *x = T->nil; // 如果 y 是后继节点情况，x 是后继节点的补充节点
if ((z->left == T->nil) || (z->right == T->nil)) {
// z 没有完整的两个节点
y = z;
} else {
// z 有两个子节点，找到后继节点，就是右子树的最小后辈节点
y = rbtree_successor(T, z);
}
// 此刻的 y 都是没有完整的两个子节点
if (y->left != T->nil) {
x = y->left;
} else {
x = y->right; // 修复：总是设置x，即使它是叶节点
}
x->parent = y->parent;
// 关键修复：正确更新根节点指针
if (y->parent == T->nil) {
T->root = x; // 当删除根节点时（y 是根节点），x成为新根
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
// 已把 y 孤立出来了
// 这是后继点情况，把后继点的键值对迁移到之前想要删除的点上
if (y != z) {
// 保存原始键值
KEY_TYPE tempKey = z->key;
void* tempValue = z->value;
// 更新z节点为y的值
z->key = y->key;
z->value = y->value;
// 更新y节点为原始z的值
y->key = tempKey;
y->value = tempValue;
}
// Y 已经被删去了，上面的步骤中的删除可以不做，跳过。
// 上面的所有讨论，都有 Y 关于其父 P 的右对称版本，代码方面就是左的变右，右的变左。
if (y->color == BLACK) {
rbtree_delete_fixup(T, x); // x 可以是指代了父节点的叶子结点，此时 X 就是叶子结点的深复制。
}
return y; // y 就是实际被删除的那一个
}
在执行删除操作后对红黑树的修复函数。
// 本代码实际上有 8 种情况，但整体是有相互对称的，故而只需详细介绍 4 种情况。
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {
// 必须要注意，后继点的左子点只会是叶结点，只可能是拥有右子节点或者无子节点，于是问题被归纳了
// x 如果为红色，是没必要如此复杂处理的，我们只需要让其变为黑点即可重新让本支路的黑高 +1，这就是 while 大循环正下方的———— x->color = BLACK ————的意义
// x 如果是黑色，那么只能是叶子结点，但由于其指明了父节点，也是可以适用这函数的。在此情况下，绝大部分情况都是可以一次过解决的。
/* 唯独以下这种情况，只能向上递归处理，把黑高不平衡问题向上传递，期待更高一级的调度解决————这就是 ”双黑问题“ ————此刻的黑叶子就是双黑点。
P
/ \
叶_X W_B (下面全是叶结点)
经过处理后
P_B_X (意思是原来的 P 点变成黑点，同时还把 X 的标记转移到 P 点上，进入下一个循环)
/ \
叶 W_R (下面全是叶结点)
这是一种等价处理方法，局部虽然平衡了，但整体黑高却是降低了一层，相当于在祖父节点处删去了一个黑色的左子节点
*/
// 我们可以这么思考问题，我们不着急把染色问题一次过解决，而是把所有原本可以一次过解决的问题，统统归结到 “双黑” 问题，即局部平衡，但整体而言确是黑高 -1 需要更高一级的调度
// 原本可以一过解决的问题转化成 ”双黑“ 问题，那么就会有八种情况 （有一半是对称的）
// 解决问题的唯二依据是迭代后的 X 的父节点是否是红点，以及 X 是否为根节点（原因是 X 的子系已经局部平衡了，然而根节点不再有旁系，故而局部平衡等于全局平衡）
// 这种设计的代码复用率会大幅提高，也是最简单的。
while ((x != T->root) && (x->color == BLACK)) {
// 此刻我们正式进入了 “双黑” 问题的论域之中，因为所删除的点是黑点，补充上来的点还是黑点（不能直接染黑了事）。
if (x == x->parent->left) {
// X 点是在其父节点的左手端
// 情况一：这是处理 z 本是有双子节点而后找到对应的后继节点的情况.
// 情况二：所删点无正常的子节点（只有叶结点）
// 还可以是更抽象的复杂的双黑问题。
rbtree_node *w= x->parent->right; // 对应于左手段的 X，W 是其右兄弟节点
if (w->color == RED) {
// 对应于 p4--> 步骤：1、W 染成黑色；2、P 点左旋，并且染成红色；3、把 W 的记号转移到当前 X 的兄弟节点上 。进入下一个循环，X 并没有更新.
// 该情况并没有把问题上传，而是 ”平级调动“
w->color = BLACK;
x->parent->color = RED;
rbtree_left_rotate(T, x->parent);
if (w->parent == T->nil) { // 更新根节点
T->root = w;
}
w = x->parent->right;
continue;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
// 对应于 p1--> 步骤：1、把 W 染红；2、P 点染黑；3、X 的记号迁移到 P 点。进入下一个循环
w->color = RED;
x->parent->color = BLACK;
x = x->parent;
// 若 P 节点本身是根节点，它还会是根节点，最顶端是根本没迁移的
} else {
if (w->right->color == BLACK) {
// p3--> 步骤：1、W 的左子节点染成黑色，W 自身染红；2、W 点右旋，把 W 的记号转移到 W 的父节点。3、套用 p2 方法
w->left->color = BLACK;
w->color = RED;
rbtree_right_rotate(T, w);
w = x->parent->right;
}
// p2--> 步骤：1、W 的右子节染黑，W 染成 P 点的颜色；2、P 点左旋，P 点变黑；3、此时已经平衡了，可以跳出循环了。
w->right->color = BLACK;
w->color = x->parent->color;
w->parent->color = BLACK;
rbtree_left_rotate(T, x->parent);
if (w->parent == T->nil) { // 更新根节点
T->root = w;
}
return;
//x = T->root;
}
} else {
// 所删节点（右手端的黑点）无子节点的情况
// 整体与上一个代码对称，此时的 X 是在右手端。
rbtree_node *w = x->parent->left; // 对应于右手端的 X，W 是其左兄弟节点
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rbtree_right_rotate(T, x->parent);
if (w->parent == T->nil) { // 更新根节点
T->root = w;
}
w = x->parent->left;
continue;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
w->color = RED;
x->parent->color = BLACK;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rbtree_left_rotate(T, w);
w = x->parent->left;
}
w->left->color = BLACK;
w->color = x->parent->color;
x->parent->color = BLACK;
rbtree_right_rotate(T, x->parent);
if (w->parent == T->nil) { // 更新根节点
T->root = w;
}
return;
}
}
}
x->color = BLACK;
}
搜索函数
经过以上的数据结构构造，我们已经成功架构了红黑树，这时候我们再给出红黑树的搜索函数，它的时间复杂度是 O ( ln N ) O(\ln N) O(lnN)
// 根据以上的数据结构构造，搜素算法的时间复杂度得以变为 O(log N)
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {
rbtree_node *node = T->root;
while (node != T->nil) {
if (key < node->key) {
node = node->left;
} else if (key > node->key) {
node = node->right;
} else {
return node;
}
}
return T->nil;
}
辅助性的打印函数
递归打印。递归函数有三元素，边界条件、递归向下展开、回溯。
// 这是递归打印
void rbtree_traversal(rbtree *T, rbtree_node *node) {
if (node != T->nil) {
rbtree_traversal(T, node->left);
printf("key:%d, color:%d\n", node->key, node->color);
rbtree_traversal(T, node->right);
}
}
在这个代码里面
边界条件：node != T->nil，是函数运行的结束条件
递归向下：即调用递归函数的上方代码，一开始便在执行，直至最内层
回溯：即展开递归函数的下方代码，回溯是展开到最内层才开始执行
设计任务测试代码能否运行正常——主函数
我们测试的任务是
1、先输入 20 个数据节点，组织成红黑树
2、逐个把他们删除后又把他们插入回来
目的是检验插入操作和删除操作是否正常。正常出现的现象是，红黑树一个节点都没有被删除，但是红黑树的物理结构发生改变，比如有些点之前是根节点，之后就不再是根节点了。因为红黑树本身就是动态地自平衡算法。
int main() {
int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};
//int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98};
rbtree *T = (rbtree *)malloc(sizeof(rbtree));
if (T == NULL) {
printf("malloc failed\n");
return -1;
}
T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
T->nil->color = BLACK;
T->root = T->nil;
rbtree_node *node = T->nil;
int i = 0;
for (i = 0;i <20;i ++) {
node = (rbtree_node*)malloc(sizeof(rbtree_node));
node->key = keyArray[i];
node->value = NULL;
rbtree_insert(T, node);
}
rbtree_traversal(T, T->root);
printf("----------------------------------------\n");
for (i = 0;i < 20;i ++) {
rbtree_node *node = rbtree_search(T, keyArray[i]); // 想要删除的目标点
rbtree_node *cur = rbtree_delete(T, node); // 实际要删除的结构点，cur 是一个深复制而非浅复制
rbtree_insert(T, cur);
//free(cur); // 释放实际删除的节点
rbtree_traversal(T, T->root);
printf("----------------------------------------\n");
}
}
代码运行效果
代码编译
qiming@qiming:~/share/CTASK/data-structure$ gcc -o rb rbtree.c
代码运行
qiming@qiming:~/share/CTASK/data-structure$ ./rb
key:9, color:2
key:12, color:1
key:13, color:1
key:14, color:2
key:15, color:1
key:17, color:2
key:18, color:1
key:19, color:2
key:20, color:1
key:21, color:1
key:23, color:2
key:24, color:2
key:25, color:2
key:26, color:2
key:35, color:2
key:38, color:1
key:47, color:2
key:49, color:1
key:67, color:2
key:98, color:1
----------------------------------------
key:9, color:2
key:12, color:1
key:13, color:1
key:14, color:2
key:15, color:1
key:17, color:2
key:18, color:1
key:19, color:2
key:20, color:1
key:21, color:2
key:23, color:2
key:24, color:1
key:25, color:2
key:26, color:2
key:35, color:2
key:38, color:1
key:47, color:2
key:49, color:1
key:67, color:2
key:98, color:1
----------------------------------------
key:9, color:2
key:12, color:1
key:13, color:1
key:14, color:2
key:15, color:1
key:17, color:2
key:18, color:1
key:19, color:2
key:20, color:1
key:21, color:2
key:23, color:2
key:24, color:2
key:25, color:1
key:26, color:2
key:35, color:2
key:38, color:1
key:47, color:2
key:49, color:1
key:67, color:2
key:98, color:1
----------------------------------------
key:9, color:2
key:12, color:1
key:13, color:1 //////////////// 略去后面的内容 /////////////////
代码现象：打印了 21 次的红黑树，每一次红黑树的节点数都没变，但是某几次某几个点的颜色改变了。这说明我们的红黑树实现代码是正确的。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
17
0- 0
已为社区贡献1条内容
所有评论(0)