数据结构与算法——第9章-查找表-红黑树完整示例代码(9.8.5)

发表于 分类于 ， ， 阅读时长 ≈ 8 分钟

一 概述

1
2
1.示例代码
2.总结

二 示例代码

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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
#include <stdio.h>
#include <stdlib.h>

typedef enum {RED, BLACK} ColorType;
typedef struct RB_TREE{
    int key;
    struct  RB_TREE * left;
    struct  RB_TREE * right;
    struct  RB_TREE * p;
    ColorType color;
}RB_TREE;

typedef struct RBT_Root{
    RB_TREE* root;
    RB_TREE* nil;
}RBT_Root;

RBT_Root* rbTree_init(void);
void rbTree_insert(RBT_Root* *T, int k);
void rbTree_delete(RBT_Root* *T, int k);

void rbTree_transplant(RBT_Root* T, RB_TREE* u, RB_TREE* v);

void rbTree_left_rotate( RBT_Root* T, RB_TREE* x);
void rbTree_right_rotate( RBT_Root* T, RB_TREE* x);

void rbTree_inPrint(RBT_Root* T, RB_TREE* t);
void rbTree_prePrint(RBT_Root * T, RB_TREE* t);
void rbTree_print(RBT_Root* T);

RB_TREE* rbt_findMin(RBT_Root * T, RB_TREE* t);
RB_TREE* rbt_findMin(RBT_Root * T, RB_TREE* t){
    if(t == T->nil){
        return T->nil;
    }
    while(t->left != T->nil){
        t = t->left;
    }
    return t;
}
RBT_Root* rbTree_init(void){
    RBT_Root* T;
    T = (RBT_Root*)malloc(sizeof(RBT_Root));
    T->nil = (RB_TREE*)malloc(sizeof(RB_TREE));
    T->nil->color = BLACK;
    T->nil->left = T->nil->right = NULL;
    T->nil->p = NULL;
    T->root = T->nil;
    return T;
}

void RB_Insert_Fixup(RBT_Root* T, RB_TREE* x){
    //首先判断其父结点颜色为红色时才需要调整；为黑色时直接插入即可，不需要调整
    while (x->p->color == RED) {
        //由于还涉及到其叔叔结点，所以此处需分开讨论，确定父结点是祖父结点的左孩子还是右孩子
        if (x->p == x->p->p->left) {
            RB_TREE * y = x->p->p->right;//找到其叔叔结点
            //如果叔叔结点颜色为红色，此为第 1 种情况，处理方法为：父结点颜色改为黑色；叔叔结点颜色改为黑色；祖父结点颜色改为红色，将祖父结点赋值为当前结点，继续判断；
            if (y->color == RED) {
                x->p->color = BLACK;
                y->color = BLACK;
                x->p->p->color = RED;
                x = x->p->p;
            }else{
                //反之，如果叔叔结点颜色为黑色，此处需分为两种情况：1、当前结点时父结点的右孩子；2、当前结点是父结点的左孩子
                if (x == x->p->right) {
                    //第 2 种情况：当前结点时父结点的右孩子。解决方案：将父结点作为当前结点做左旋操作。
                    x = x->p;
                    rbTree_left_rotate(T, x);
                }else{
                    //第 3 种情况：当前结点是父结点的左孩子。解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理。
                    x->p->color = BLACK;
                    x->p->p->color = RED;
                    rbTree_right_rotate(T, x->p->p);
                }
            }
        }else{//如果父结点时祖父结点的右孩子，换汤不换药，只需将以上代码部分中的left改为right即可，道理是一样的。
            RB_TREE * y = x->p->p->left;
            if (y->color == RED) {
                x->p->color = BLACK;
                y->color = BLACK;
                x->p->p->color = RED;
                x = x->p->p;
            }else{
                if (x == x->p->left) {
                    x = x->p;
                    rbTree_right_rotate(T, x);
                }else{
                    x->p->color = BLACK;
                    x->p->p->color = RED;
                    rbTree_left_rotate(T, x->p->p);
                }
            }
        }
    }
    T->root->color = BLACK;
}
//插入操作分为 3 步：1、将红黑树当二叉查找树，找到其插入位置；2、初始化插入结点，将新结点的颜色设为红色；3、通过调用调整函数，将二叉查找树重新改为红黑树
void rbTree_insert(RBT_Root**T, int k){
    //1、找到其要插入的位置。解决思路为：从树的根结点开始，通过不断的同新结点的值进行比较，最终找到插入位置
    RB_TREE * x, *p;
    x = (*T)->root;
    p = x;

    while(x != (*T)->nil){
        p = x;
        if(k<x->key){
            x = x->left;
        }else if(k>x->key){
            x = x->right;
        }else{
            printf("\n%d已存在\n",k);
            return;
        }
    }
    //初始化结点，将新结点的颜色设为红色
    x = (RB_TREE *)malloc(sizeof(RB_TREE));
    x->key = k;
    x->color = RED;
    x->left = x->right =(*T)->nil;
    x->p = p;
    //对新插入的结点，建立与其父结点之间的联系
    if((*T)->root == (*T)->nil){
        (*T)->root = x;
    }else if(k < p->key){
        p->left = x;
    }else{
        p->right = x;
    }
    //3、对二叉查找树进行调整
    RB_Insert_Fixup((*T),x);
}
void rbTree_transplant(RBT_Root* T, RB_TREE* u, RB_TREE* v){
    if(u->p == T->nil){
        T->root = v;
    }else if(u == u->p->left){
        u->p->left=v;
    }else{
        u->p->right=v;
    }
    v->p = u->p;
}
void RB_Delete_Fixup(RBT_Root**T,RB_TREE*x){
    while(x != (*T)->root && x->color == BLACK){
        if(x == x->p->left){
            RB_TREE* w = x->p->right;
            //第 1 种情况：兄弟结点是红色的
            if(RED == w->color){
                w->color = BLACK;
                w->p->color = RED;
                rbTree_left_rotate((*T),x->p);
                w = x->p->right;
            }
            //第2种情况：兄弟是黑色的，并且兄弟的两个儿子都是黑色的。
            if(w->left->color == BLACK && w->right->color == BLACK){
                w->color = RED;
                x = x->p;
            }
            //第3种情况
            if(w->left->color == RED && w->right->color == BLACK){
                w->left->color = BLACK;
                w->color = RED;
                rbTree_right_rotate((*T),w);
                w = x->p->right;
            }
            //第4种情况
            if (w->right->color == RED) {
                w->color = x->p->color;
                x->p->color = BLACK;
                w->right->color = BLACK;
                rbTree_left_rotate((*T),x->p);
                x = (*T)->root;
            }
        }else{
            RB_TREE* w = x->p->left;
            //第 1 种情况
            if(w->color == RED){
                w->color = BLACK;
                x->p->color = RED;
                rbTree_right_rotate((*T),x->p);
                w = x->p->left;
            }
            //第 2 种情况
            if(w->left->color == BLACK && w->right->color == BLACK){
                w->color = RED;
                x = x->p;
            }
            //第 3 种情况
            if(w->left->color == BLACK && w->right->color == RED){
                w->color = RED;
                w->right->color = BLACK;
                w = x->p->left;
            }
            //第 4 种情况
            if (w->right->color == BLACK){
                w->color=w->p->color;
                x->p->color = BLACK;
                w->left->color = BLACK;
                rbTree_right_rotate((*T),x->p);
                x = (*T)->root;
            }
        }
    }
    x->color = BLACK;//最终将根结点的颜色设为黑色
}
void rbTree_delete(RBT_Root* *T, int k){
    if(NULL == (*T)->root){
        return ;
    }
    //找到要被删除的结点
    RB_TREE * toDelete = (*T)->root;
    RB_TREE * x = NULL;
    //找到值为k的结点
    while(toDelete != (*T)->nil && toDelete->key != k){
        if(k<toDelete->key){
            toDelete = toDelete->left;
        }else if(k>toDelete->key){
            toDelete = toDelete->right;
        }
    }
    if(toDelete == (*T)->nil){
        printf("\n%d 不存在\n",k);
        return;
    }
    //如果两个孩子，就找到右子树中最小的结点，将之代替，然后直接删除该结点即可
    if(toDelete->left != (*T)->nil && toDelete->right != (*T)->nil){
        RB_TREE* alternative = rbt_findMin((*T), toDelete->right);
        k = toDelete->key = alternative->key;//这里只对值进行复制，并不复制颜色，以免破坏红黑树的性质
        toDelete = alternative;
    }
    //如果只有一个孩子结点（只有左孩子或只有右孩子），直接用孩子结点顶替该结点位置即可（没有孩子结点的也走此判断语句）。
    if(toDelete->left == (*T)->nil){
        x = toDelete->right;
        rbTree_transplant((*T),toDelete,toDelete->right);
    }else if(toDelete->right == (*T)->nil){
        x = toDelete->left;
        rbTree_transplant((*T),toDelete,toDelete->left);
    }
    //在删除该结点之前，需判断此结点的颜色：如果是红色，直接删除，不会破坏红黑树；若是黑色，删除后会破坏红黑树的第 5 条性质，需要对树做调整。
    if(toDelete->color == BLACK){
        RB_Delete_Fixup(T,x);
    }
    //最终可以彻底删除要删除的结点，释放其占用的空间
    free(toDelete);
}

//T表示为树根，x 表示需要进行左旋的子树的根结点
void rbTree_left_rotate( RBT_Root* T, RB_TREE* x){
    RB_TREE* y = x->right;//找到根结点的右子树

    x->right = y->left;//将右子树的左孩子移动至结点 x 的右孩子处
    if(x->right != T->nil){//如果 x 的右子树不是nil，需重新连接 右子树的双亲结点为 x
        x->right->p = x;
    }
    y->p = x->p;//设置 y 的双亲结点为 x 的双亲结点
    //重新设置 y 的双亲结点同 y 的连接，分为 2 种情况：1、原 x 结点本身就是整棵树的数根结点，此时只需要将 T 指针指向 y；2、根据 y 中关键字同其父结点关键字的值的大小，判断 y 是父结点的左孩子还是右孩子
    if(y->p == T->nil){
        T->root = y;
    }else if(y->key < y->p->key){
        y->p->left = y;
    }else{
        y->p->right = y;
    }
    y->left = x;//将 x 连接给 y 结点的左孩子处
    x->p = y;//设置 x 的双亲结点为 y。
}

void rbTree_right_rotate( RBT_Root* T, RB_TREE* x){
    RB_TREE * y = x->left;
    x->left = y->right;
    if(T->nil != x->left){
        x->left->p = x;
    }
    y->p = x->p;
    if(y->p == T->nil){
        T->root = y;
    }else if(y->key < y->p->key){
        y->p->left= y;
    }else{
        y->p->right = y;
    }
    y->right = x;
    x->p = y;
}
void rbTree_prePrint(RBT_Root* T, RB_TREE* t){
    if(T->nil == t){
        return;
    }
    if(t->color == RED){
        printf("%dR ",t->key);
    }else{
        printf("%dB ",t->key);
    }
    rbTree_prePrint(T,t->left);
    rbTree_prePrint(T,t->right);
}
void rbTree_inPrint(RBT_Root* T, RB_TREE* t){
    if(T->nil == t){
        return ;
    }
    rbTree_inPrint(T,t->left);
    if(t->color == RED){
        printf("%dR ",t->key);
    }else{
        printf("%dB ",t->key);
    }
    rbTree_inPrint(T,t->right);
}

//输出红黑树的前序遍历和中序遍历的结果
void rbTree_print(RBT_Root* T){
    printf("前序遍历 ：");
    rbTree_prePrint(T,T->root);
    printf("\n");
    printf("中序遍历 ：");
    rbTree_inPrint(T,T->root);
    printf("\n");
}

int main(){
    RBT_Root* T = rbTree_init();

    rbTree_insert(&T,3);
    rbTree_insert(&T,5);
    rbTree_insert(&T,1);
    rbTree_insert(&T,2);
    rbTree_insert(&T,4);
    rbTree_print(T);
    printf("\n");
    rbTree_delete(&T,3);
    rbTree_print(T);

    return 0;
}

运行结果

1
2
3
4
前序遍历 ：3B 1B 2R 5B 4R
中序遍历 ：1B 2R 3B 4R 5B
前序遍历 ：4B 1B 2R 5B
中序遍历 ：1B 2R 4B 5B

三 总结

1
2
3
4
5
6
7
8
9
本节介绍的红黑树，虽隶属于二叉查找树，但是二叉查找树的时间复杂度会受到其树深度的影响，
而红黑树可以保证在最坏情况下的时间复杂度仍为O(lgn)。
当数据量多到一定程度时，使用红黑树比二叉查找树的效率要高。

同平衡二叉树相比较，红黑树没有像平衡二叉树对平衡性要求的那么苛刻，虽然两者的时间复杂度相同，
但是红黑树在实际测算中的速度要更胜一筹！

提示：平衡二叉树的时间复杂度是 O(logn)，红黑树的时间复杂度为 O(lgn)，
两者都表示的都是时间复杂度为对数关系（lg 函数为底是 10的对数，用于表示时间复杂度时可以忽略）。

四 参考

  • C语言中文网—红黑树（更高级的二叉查找树）算法详解