红黑树（Red Black Tree）（C语言实现、200行精简版）_c语言 红黑树代码

红黑树

红黑树（Red Black Tree）是一种自平衡的二叉搜索树，与AVL树类似，在其上进行的插入、删除、查找操作的平均时间复杂度均为O(logn)。

但与AVL树不同的是，红黑树的平衡不是非常严格的平衡（即左右子树高度差不超过1），它牺牲了部分平衡性来换取了插入、删除时的少量旋转操作。

一、关于红黑树的叶子结点：

​ 红黑树特别区分了中间结点与叶子结点。在二叉搜索树中，叶子结点与中间结点一般不做区分，两者的区别仅在于有没有子结点（叶结点的子结点为$NULL$，视为没有子结点）。虽然在红黑树中也可以这样，但是为了方便解释与实现，一般对叶子结点进行了区分：叶子结点不存储数据，只是充当树在此结束的标志。

Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL() {
    NIL->color = 1;
    NIL->key = 0;
    NIL->lchild = NIL->rchild = NIL;
    return ;
}
1
2
3
4
5
6
7
8
9

__attribute__介绍

　　__attribute__可以设置函数属性(Function Attribute)、变量属性(Variable Attribute)和类型属性(Type Attribute)。__attribute__前后都有两个下划线，并且后面会紧跟一对原括弧，括弧里面是相应的__attribute__参数

　　__attribute__语法格式为：__attribute__ ( ( attribute-list ) )

　　若函数被设定为constructor属性，则该函数会在main（）函数执行之前被自动的执行。
　　类似的，若函数被设定为destructor属性，则该函数会在main（）函数执行之后或者exit（）被调用后被自动的执行。
1
2
3
4
5
6
7
8

二、红黑树的5条性质：

1. 结点非黑既红
2. 根结点是黑色
3. 叶子（NIL）结点是黑色
4. 红色结点下面接两个黑色结点（即有父子关系的两个结点不能均为红色）
5. 从任一结点出发，到其每个叶子结点的所有简单路径上的黑色结点的数量相同。（这个黑结点数量也被称为黑高）

基于这5个性质，红黑树能够保证从根结点到叶子结点最长深度不会超过最短深度的2倍，从而保证了红黑树的平衡性。

因为最长路径即为红黑交替出现，而最短路径即为全部为黑结点。又由于性质5，所以这两条路径上的黑色结点数目一定相同，根结点与叶结点均为黑色，最长路径上多出的红色结点数目一定不会多于黑色结点的数目。

也正因为红黑树平衡性是通过黑高来进行维护的，所以在其结点上不用存储树的高度（本质上红黑树也是通过树高(黑高)维护平衡的）。

三、学习诀窍

• 插入：

1. 理解红黑树的插入调整，要站在祖父结点向下进行调整
2. 插入调整，主要就是为了解决双红情况
3. 新插入的结点一定是红色。插入黑色结点一定会产生冲突，违反性质5，插入红色结点，不一定产生冲突

• 删除：

1. 理解红黑树的删除调整，要站在父结点向下进行调整
2. 删除红色结点不会对树的平衡产生影响
3. 删除度为1的黑色结点，可以把其孤儿子树挂到父结点上，并把孤儿子树根结点染黑（度为1的黑色节点，唯一子孩子，一定是红色）
4. 删除度为2的黑色结点，可以把其转换成删除度为1或度为0的情况
5. 删除度为0的结点会产生双重黑NIL结点。删除调整，主要就是为了干掉双重黑

• 整体动态感：

1. 把每一种情况，想象成一棵大的红黑树中的局部子树
2. 局部调整的时候，为了不影响全局，调整前后的路径上黑色结点数量相同

四、插入调整策略

• 情况一：叔叔结点为红色的时候，修改三元组小帽子，改成红黑黑。(回溯阶段解决冲突的祖父结点一定是黑色）

• 情况二：叔叔结点为黑色的时候，参考 $AVL$ 树的失衡情况，分成 $LL,LR,RL,RR$, 先参考 $AVL$ 树的旋转调整策略，然后再修改三元组的颜色，有两种调整策略：红色上浮，红色下沉。

红色上浮：可能会导致与父结点冲突

红色下沉：可能会导致与新插入的子结点冲突

分析下图：

1、双红结点下还有其它结点说明此图发生在插入之后的回溯阶段（要想象成一个大红黑树的其中一小部分）

2、$LL$失衡情况下结点的确定性：

1. $20$结点（祖父）确定为黑色

   2. $16、10$结点（$LL$失衡）确定为红色
   3. 因为是情况二，所以$25$（叔叔结点）为黑色，那么$8，12，18$都存在并且都为黑色(黑高)。如果叔叔结点为$NIL$结点，其它三个结点也都为$NIL$结点（也是黑色）
   4. 此图中只有$19$号结点为特例结点（此情况下不必然存在）

注意：两大类情况，包含 $8$ 种小情况

五、删除调整策略

• 删除度为$1$的黑色结点

删除度为$1$的黑色结点，可以把其孤儿子树挂到父结点上，并把孤儿子树根结点染黑（度为$1$的黑色节点，唯一子孩子，一定是红色）

---

• 删除度为$0$的黑色结点

当删除度为$0$的黑色结点时会产生双重黑结点（删除调整主要是为了干掉双重黑）

---

• 干掉双重黑的三种情况(策略)：

情况一：双重黑结点的兄弟结点是黑色，兄弟结点下面的两个子结点也是黑色

调整策略：父结点增加一重黑色，双重黑与兄弟结点分别减少一重黑色，从而使双重黑结点向上传递

如果$43$号结点为红色，那么向上传递后$43$号变为普通黑(即干掉了双重黑)

如果$43$号结点为黑色并且又是整颗红黑树的根结点，那么将其染发成普通黑结点(即干掉了双重黑)

如果$43$号结点为黑色，又不是根结点，那么继续向上传递，有可能过程中通过其它情况干掉双重黑。

情况二：双重黑结点的兄弟结点是黑色，兄弟结点下面存在红色子结点

（一）$RR$失衡

$R$（兄弟）$R$（右子结点）为红色

调整策略：左旋（旋转后直接干掉双重黑），新根改成原根的颜色，将新根的两个子结点，改成黑色

策略分析：

旋转前分析$RR$失衡下结点的确定性：因为$RR$失衡，所以$28，51，72$号结点的颜色确定。又因为$72$号结点确定为红色，所以它的两个子孩子$64，85$都必为黑色。$48$号的颜色不确定，当前$48$为黑色，假设$48$号结点为红色，$42$号结点为黑色，再给$48$加个黑色右孩子结点，$RB$树依然平衡。$38$号结点的颜色也不确定，当前$38$号结点为红色，假设为黑色，只需要在$89$号结点的左子树中加一层黑色结点，$RB$树依然平衡。最后$29，42，73$号结点可有可无，即使存在颜色也不确定，可以是一个庞大的子树根。

旋转后如何调整颜色并保证不失衡：首先看$48$号结点旋转后接到$38$号结点下边，又因为$48$号结点的颜色不确定，也就是说$48$号结点有可能是红色，为了不发生冲突，只能将38号结点改成黑色。又因为旋转前从原根结点（$38$号）到每个$NIL$结点路径上的黑色结点数都为$2$，为维护黑高性质，旋转后每条路径上黑色结点数量也应为$2$。但是如果将$38$号结点改为黑色，那么左侧路径上黑色结点数量变为$3$，所以要把51号结点变为红色来保证左侧路径中黑色结点数量依旧为$2$。$51$变红后，右侧路径上黑色结点数量变为$1$，为保证右侧路径黑色结点数量依旧为$2$，还要将72号结点变为黑色。此时在$38$号结点为红色时，无论$48$号结点颜色为何，该调整策略都不会产生冲突($51$变红，$38，72$变黑)。但是$38$号结点的颜色不确定也有可能为黑色，所以最终的完美调整策略是左旋，新根改成原根的颜色，将新根的两个子结点，改成黑色（51号变为38的颜色，$38，72$号变黑）

（二）$RL$失衡

$R$（兄弟）$L$（左子结点）为红色，右子结点不为红色

调整策略：通过小右旋（对调新根与原根颜色）转换成$RR$失衡

策略分析：

旋转前分析$RR$失衡下结点的确定性：因为$RL$失衡，所以72，51，85号结点的颜色确定。因为51号结点确定为红色，那么48，64号结点确定为黑色。42，87号结点不确定存在，即使存在颜色也不确定，有可能是一个庞大子树的根。

旋转后如何调整颜色并保证不失衡：旋转前每个路径上两个黑色结点，旋转后左侧路径上一个黑色结点，所以要把51号结点染成黑色，来保证左侧路径。这时右侧路径变成了三个黑色结点，此时要把85号结点染成红色，来保证右侧路径。所以最终策略是，原根和新根对调颜色。

（三）$LL$失衡

同理$RR$失衡

（四）$LR$失衡

同理$RL$失衡

情况三：双重黑结点的兄弟结点是红色

兄弟结点红色，通过旋转，转变成兄弟结点是黑色的情况

六、代码演示

1. 插入调整，发正在递归的回溯阶段

2. 插入调整代码中，使用 $goto$ 语句，$8$行代码，变成了$4$行

3. 处理根结点一定是黑色，通过代码封装，$insert->\_\_insert$（染发）

4. 进行 $LR/RL$ 类型判断的时候，不能判断$LL/RR$子树是否为黑色，$LL/RR$子树有可能是 $NIL$ 节点，在某些特殊情况下(删除调整回溯阶段)，读到的颜色可能是双重黑(程序中$NIL$结点通用)，取而代之的判断方法就是【$LL$ 子树不是红色】。

/*************************************************************************
        > File Name: RB_tree.c
        > Author: Luzelin
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int color, key;
    struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL() {
    NIL->color = 1;
    NIL->key = 0;
    NIL->lchild = NIL->rchild = NIL;
    return ;
}

Node* GetNewNode(int val) {
    Node *s = (Node *)malloc(sizeof(Node));
    s->color = 0;
    s->key = val;
    s->lchild = s->rchild = NIL;
    return s;
}

#define LC lchild->color
#define RC rchild->color

int has_red_child(Node *root) {
    return (root->LC == 0 || root->RC == 0 ? 1 : 0);
}

Node* L_rotate(Node *root) {
    Node *p = root->rchild;
    root->rchild = p->lchild;
    p->lchild = root;
    return p;
}

Node* R_rotate(Node *root) {
    Node *p = root->lchild;
    root->lchild = p->rchild;
    p->rchild = root;
    return p;
}

//站在祖父节点 调整插入失衡(处理双红情况)
Node* Balance_Insert(Node *root) {
    /***子结点都为黑色***/
    //如果当前节点的两个子结点没有红色，那么就不可能发生儿孙冲突
    if (!has_red_child(root))  return root;
    
    //flag 0 平衡   1 左子树失衡  2 右子树失衡
    int flag = 0;

    //if (root->LC == 0 && root->RC == 0)  goto end;
    /***子结点都为红色***/
    //如果当前节点的两个子结点都为红色，并且还存在红色孙子节点(失衡态)，此时红色上浮。
    //分析，此时当前节点必为黑色，并且最多只有一个孙子节点可能是红色
    if (root->LC == 0 && root->RC == 0) {
        if (has_red_child(root->lchild) || has_red_child(root->rchild))  goto end;
    }

    /***子结点一黑一红***/
    //如果失衡找到失衡侧
    if (root->LC == 0 && has_red_child(root->lchild))  flag = 1;
    if (root->RC == 0 && has_red_child(root->rchild))  flag = 2;
    if (flag == 0)  return root;  //平衡
    //分情况处理失衡态
    if (flag == 1) {
        if (root->lchild->RC == 0)  root->lchild = L_rotate(root->lchild);
        root = R_rotate(root);
    } else {
        if (root->rchild->LC == 0)  root->rchild = R_rotate(root->rchild);
        root = L_rotate(root);
    }
    //红色上浮
    end:
    root->color = 0;
    root->LC = root->RC = 1;
    return root;
}

Node* __Insert(Node *root, int val) {
    if (root == NIL)  return GetNewNode(val);
    if (val < root->key)  root->lchild = __Insert(root->lchild, val);
    else if (val > root->key)  root->rchild = __Insert(root->rchild, val);
    return Balance_Insert(root);
}

Node* Insert(Node *root, int val) {
    root = __Insert(root, val);
    //封装染发
    root->color = 1;
    return root;
}

int precursor(Node *root) {
    root = root->lchild;
    while (root->rchild != NIL)  root = root->rchild;
    return root->key;
}

//站在父结点 调整删除失衡(处理双重黑)
Node* Balance_Erase(Node *root) {
    //如果当前节点的子结点没有双重黑则平衡
    /***子结点没有双重黑***/
    if (root->LC != 2 && root->RC != 2)  return root;
    
    //存在双重黑节点，并且其兄弟节点为红色
    /***子结点中存在双重黑，并且兄弟节点为红色***/
    if (has_red_child(root)) {
        root->color = 0;  //原根红
        int flag = 0;
        //红色兄弟在左侧，右旋(向双重黑方向)
        if (root->LC == 0) {
            root = R_rotate(root);
            flag = 1;
        } else {
        //红色兄弟右侧，左旋(向双重黑方向)
            root = L_rotate(root);
            flag = 2;
        }
        root->color = 1;  //新根黑
        //因为旋转之后双重黑节点到了当前节点的孙子节点的位置，所以需要向下一步走(站在父结点处理删除失衡)
        if (flag == 1)  root->rchild = Balance_Erase(root->rchild);
        if (flag == 2)  root->lchild = Balance_Erase(root->lchild);
        return root;
    }

    //存在双重黑节点，并且其兄弟节点为黑色，兄弟节点的两个子结点也都为黑色(父结点+1重黑，两个子结点-1重黑)
    /***子结点中存在双重黑，兄弟是黑色，兄弟的孩子都是黑色***/
    if ((root->LC == 1 && !has_red_child(root->lchild)) || (root->RC == 1 && !has_red_child(root->rchild))) {
        root->color += 1;
        root->LC -= 1;
        root->RC -= 1;
        return root;
    }

    //存在双重黑节点，并且其兄弟节点为黑色，兄弟节点的子结点中存在红色节点
    /***子结点中存在双重黑，兄弟是黑色，兄弟有红色孩子***/
    if (root->RC == 2) {
        if (root->lchild->LC != 0) {
            //LR失衡
            root->LC = 0;   //原红
            root->lchild = L_rotate(root->lchild);
            root->LC = 1;   //新黑
        }
        root = R_rotate(root);    //LL失衡
        root->color = root->RC;   //新根颜色等于原根颜色
        root->rchild->RC = 1;     //干掉双重黑
    } else {
        if (root->rchild->RC != 0) {
            //RL失衡
            root->RC = 0;   //原红
            root->rchild = R_rotate(root->rchild);
            root->RC = 1;   //新黑
        }
        root = L_rotate(root);    //RR失衡
        root->color = root->LC;   //新根颜色等于原根颜色
        root->lchild->LC = 1;     //干掉双重黑
    }
    root->LC = root->RC = 1;      //两个子结点变黑色
    return root;
}

Node* __Erase(Node *root, int val) {
    if (root == NIL)  return root;
    if (val < root->key)  root->lchild = __Erase(root->lchild, val);
    else if (val > root->key)  root->rchild = __Erase(root->rchild, val);
    else {
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *p = (root->lchild != NIL ? root->lchild : root->rchild);
            p->color += root->color;
            free(root);
            return p;
        } else {
            int k = precursor(root);
            root->key = k;
            root->lchild = __Erase(root->lchild, k);
        }
    }
    return Balance_Erase(root);
}

Node* Erase(Node *root, int val) {
    root = __Erase(root, val);
    //封装染发
    root->color = 1;
    return root;
}

void output(Node *root) {
    if (root == NIL)  return ;
    output(root->lchild);
    printf("%d %d %d %d\n", root->key, root->color, root->lchild->key, root->rchild->key);
    output(root->rchild);
    return ;
}

int main() {
    Node *root = NIL;
    int x, y;
    while (scanf("%d%d", &x, &y) != EOF) {
        if (x == 1)  root = Insert(root, y);
        else if (x == 2)  root = Erase(root, y);
        else if (x == 3)  output(root);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216