红黑树C语言实现

发表于 更新于 分类于 Waline： 阅读次数：

节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
enum color_t {RED,BLACK};

typedef int Type;

typedef struct RBTreeNode{
    struct RBTreeNode *left;
    struct RBTreeNode *right;
    struct RBTreeNode *parent;
    enum color_t color;
    Type key;
}Node;

//根节点
typedef struct RBRoot{
    Node* root;
    Node *nil;//叶子（空指针）
}rb_root;

插入

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
//插入与AVL树完全相同，最后调整即可
//新插入指针初始化颜色为红色
void rb_insert(rb_root* T,Node* z){
    Node* y=T->nil;
    Node* x=T->root;
    while(x!=T->nil){
        y=x;
        if(x->key<z->key){
            x=x->right;
        }else x=x->left;
    }
    z->parent=y;
    if(y==T->nil) T->root=z;
    else if(z->key<y->key) y->left=z;
    else y->right=z;
    z->left=z->right=T->nil;
    z->color=RED;
    rb_insert_fix(T,z); //修正红黑树
}
//创建新节点
void rb_insert_type(rb_root* T,Type key){
    Node *p=(Node*)malloc(sizeof(Node));
    p->color=RED;
    p->key=key;
    p->left=p->right=p->parent=T->nil;
    rb_insert(T,p);
}

插入修正函数

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
//只有插入节点的父节点为红色才需要修正
void rb_insert_fix(rb_root* T,Node* z){
    //case1:z就是根节点，直接修正为黑色
    while(z->parent!=T->nil&&z->parent->color==RED){
        if(z->parent==z->parent->parent->left){//LL或者LR两种情形
            Node *y=z->parent->parent->right;//y为unlce（叔叔）节点
            if(y!=T->nil&&y->color==RED){//case2：uncle节点为红色
                z->parent->color=BLACK;
                y->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }else if(z==z->parent->right){//case2：uncle节点为黑色，z为父节点的右子树（LR）
                z=z->parent;
                rotate_left(T,z);
            }else{//case3：unlce为黑色，z为父节点的左子树（LL）
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rotate_right(T,z->parent->parent);
            }
        }else{//RR或者RL两种情形，代码完全对称
            Node* y=z->parent->parent->left;
            if(y!=T->nil&&y->color==RED){//RL或者RR，uncle为红色
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }else if(z==z->parent->left){//RL,uncle为黑色
                z=z->parent;
                rotate_right(T,z);
            }else{//RR,uncle为黑色
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rotate_left(T,z->parent->parent);
            }
        }
    }
    T->root->color=BLACK;
}

左转、右转

左转右转 
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
void rotate_left(rb_root *T,Node *x){
    Node* y=x->right;
    x->right=y->left;
    if(y->left!=T->nil){
        y->left->parent=x;
    }
    y->parent=x->parent;
    if(x->parent==T->nil) T->root=y;
    else if(x==x->parent->left){
        x->parent->left=y;
    }else{
        x->parent->right=y;
    }
    y->left=x;
    x->parent=y;
}

void rotate_right(rb_root* T,Node* x){
    Node* y=x->left;
    x->left=y->right;
    if(y->right!=T->nil) y->right->parent=x;
    y->parent=x->parent;
    if(x->parent==T->nil) T->root=y;
    else if(x==x->parent->left){
        x->parent->left=y;
    }else{
        x->parent->right=y;
    }
    y->right=x;
    x->parent=y;
}

节点删除

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
void rbtree_delete(rb_root* T,Node* z){
    Node *y=z;
    Node* x;
    int y_origin_color=y->color;
    if(z->left==T->nil){
        x=z->right;
        rb_transplant(T,z,x);
    }else if(z->right==T->nil){
        x=z->left;
        rb_transplant(T,z,x);
    }else{
        y=tree_minimum(T,z->right);
        y_origin_color=y->color;
        x=y->right;
        if(y->parent==z) x->parent=y;//y是被删除节点z的右孩子节点
        else {//y不是被删除节点z的子节点
            rb_transplant(T,y,y->right);
            y->right=z->right;
            y->right->parent=y;
        }
        rb_transplant(T,z,y);
        y->color=z->color;
        y->left=z->left;
        y->left->parent=y;
    }
    if(y_origin_color==BLACK)
        rbtree_delete_fix(T,x);//用y替换了被删除节点的数据，相当于y被删除了，所有要调节y下面的子树满足红黑树要求
}

Node* search(rb_root* T,Type key){
    Node* y=T->root;
    while(y!=T->nil){
        if(y->key==key) return y;
        else if(y->key<key) y=y->right;
        else y=y->left;
    }
    return NULL;
}

void delete_rbtree(rb_root* T,Type key){
    Node* t=search(T,key);
    if(t!=NULL)
        rbtree_delete(T,t);
}

删除调整函数

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
void rbtree_delete_fix(rb_root* T,Node* x){//x指向节点具有多一重的黑色属性
    while(x!=T->root&&x->color==BLACK){//x为红色直接变黑即可
        if(x==x->parent->left){//x为左侧分支
            Node* w=x->parent->right;
            if(w->color==RED){//兄弟节点为红色
                w->color=BLACK;
                x->parent->color=RED;
                rotate_left(T,x->parent);
                w=x->parent->right;
            }
            if(w->left->color==BLACK&&w->right->color==BLACK){
                w->color=RED;
                x=x->parent;
            }
            else{//case4,调整结束不再需要沿树上移，因为不存在双重属性的节点
                if(w->right->color==BLACK){
                    w->color=RED;
                    w->left->color=BLACK;
                    rotate_right(T,w);
                    w=x->parent->right;
                }
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->right->color=BLACK;
                rotate_left(T,x->parent);
                x=T->root;
            }
        }else{
            Node* w=x->parent->left;
            if(w->color==RED){
                w->color=BLACK;
                x->parent->color=RED;
                rotate_right(T,w);
                w=x->parent->left;
            }
            if(w->left->color==BLACK&&w->right->color==BLACK){
                w->color=RED;
                x=x->parent;
            }
            else{
                if(w->left->color==BLACK){
                    w->color=RED;
                    w->right->color=BLACK;
                    rotate_left(T,w);
                    w=x->parent->left;
                }
                w->color=x->parent->color;
                w->parent->color=BLACK;
                w->left->color=BLACK;
                rotate_right(T,x->parent);
                x=T->root;
            }
        }
    }
    x->color=BLACK;
}

完整代码

rbtree.h

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
#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_

enum color_t {RED,BLACK};

typedef int Type;

typedef struct RBTreeNode{
    struct RBTreeNode *left;
    struct RBTreeNode *right;
    struct RBTreeNode *parent;
    enum color_t color;
    Type key;
}Node;

typedef struct RBRoot{
    Node* root;
    Node *nil;
}rb_root;

Node* get_parent(rb_root*,Node*);

Node* get_grandfather(rb_root*,Node*);

#endif

main.c

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
#include <stdio.h>
#include <stdlib.h>
#include "rbtree.h"

Node* get_parent(rb_root *T,Node* n){
    return n==T->nil?T->nil:n->parent;
}

Node* get_grandfather(rb_root* T,Node *n){
    return get_parent(T,get_parent(T,n));
}

Node* get_sibling(rb_root* T,Node* n){
    Node *p=get_parent(T,n);
    if(p==T->nil) return T->nil;
    if(p->left==n){
        return p->right;
    }else{
        return p->left;
    }
}

Node* get_uncle(rb_root* T,Node *n){
    Node *p=get_parent(T,n);
    return get_sibling(T,p); 
}

void rotate_left(rb_root *T,Node *x){
    Node* y=x->right;
    x->right=y->left;
    if(y->left!=T->nil){
        y->left->parent=x;
    }
    y->parent=x->parent;
    if(x->parent==T->nil) T->root=y;
    else if(x==x->parent->left){
        x->parent->left=y;
    }else{
        x->parent->right=y;
    }
    y->left=x;
    x->parent=y;
}

void rotate_right(rb_root* T,Node* x){
    Node* y=x->left;
    x->left=y->right;
    if(y->right!=T->nil) y->right->parent=x;
    y->parent=x->parent;
    if(x->parent==T->nil) T->root=y;
    else if(x==x->parent->left){
        x->parent->left=y;
    }else{
        x->parent->right=y;
    }
    y->right=x;
    x->parent=y;
}

void rb_insert_fix(rb_root* T,Node* z){
    while(z->parent!=T->nil&&z->parent->color==RED){
        if(z->parent==z->parent->parent->left){//LL或者LR两种情形
            Node *y=z->parent->parent->right;
            if(y!=T->nil&&y->color==RED){
                z->parent->color=BLACK;
                y->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }else if(z==z->parent->right){//LR并且uncle为黑色
                z=z->parent;
                rotate_left(T,z);
            }else{//LL且uncle为黑色
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rotate_right(T,z->parent->parent);
            }
        }else{
            Node* y=z->parent->parent->left;
            if(y!=T->nil&&y->color==RED){//RL或者RR，uncle为红色
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            }else if(z==z->parent->left){//RL,uncle为黑色
                z=z->parent;
                rotate_right(T,z);
            }else{//RR,uncle为黑色
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rotate_left(T,z->parent->parent);
            }
        }
    }
    T->root->color=BLACK;
}

//插入与AVL树完全相同，最后调整即可
void rb_insert(rb_root* T,Node* z){
    Node* y=T->nil;
    Node* x=T->root;
    while(x!=T->nil){
        y=x;
        if(x->key<z->key){
            x=x->right;
        }else x=x->left;
    }
    z->parent=y;
    if(y==T->nil) T->root=z;
    else if(z->key<y->key) y->left=z;
    else y->right=z;
    z->left=z->right=T->nil;
    z->color=RED;
    rb_insert_fix(T,z);
}

void rb_insert_type(rb_root* T,Type key){
    Node *p=(Node*)malloc(sizeof(Node));
    p->color=RED;
    p->key=key;
    p->left=p->right=p->parent=T->nil;
    rb_insert(T,p);
}

Node* tree_minimum(rb_root* T,Node* z){
    Node* y=z;
    while(y->left!=T->nil){
        y=y->left;
    }
    return y;
}


void rb_transplant(rb_root* T,Node* u,Node* v){//把v节点接到原来u的位置
    if(u->parent==T->nil)
        T->root=v;
    else if(u==u->parent->left)
        u->parent->left=v;
    else u->parent->right=v;
    v->parent=u->parent;
}

void rbtree_delete_fix(rb_root* T,Node* x){//x指向节点具有多一重的黑色属性
    while(x!=T->root&&x->color==BLACK){//x为红色直接变黑即可
        if(x==x->parent->left){//x为左侧分支
            Node* w=x->parent->right;
            if(w->color==RED){//兄弟节点为红色
                w->color=BLACK;
                x->parent->color=RED;
                rotate_left(T,x->parent);
                w=x->parent->right;
            }
            if(w->left->color==BLACK&&w->right->color==BLACK){
                w->color=RED;
                x=x->parent;
            }
            else{//case4,调整结束不再需要沿树上移，因为不存在双重属性的节点
                if(w->right->color==BLACK){
                    w->color=RED;
                    w->left->color=BLACK;
                    rotate_right(T,w);
                    w=x->parent->right;
                }
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->right->color=BLACK;
                rotate_left(T,x->parent);
                x=T->root;
            }
        }else{
            Node* w=x->parent->left;
            if(w->color==RED){
                w->color=BLACK;
                x->parent->color=RED;
                rotate_right(T,w);
                w=x->parent->left;
            }
            if(w->left->color==BLACK&&w->right->color==BLACK){
                w->color=RED;
                x=x->parent;
            }
            else{
                if(w->left->color==BLACK){
                    w->color=RED;
                    w->right->color=BLACK;
                    rotate_left(T,w);
                    w=x->parent->left;
                }
                w->color=x->parent->color;
                w->parent->color=BLACK;
                w->left->color=BLACK;
                rotate_right(T,x->parent);
                x=T->root;
            }
        }
    }
    x->color=BLACK;
}

void rbtree_delete(rb_root* T,Node* z){
    Node *y=z;
    Node* x;
    int y_origin_color=y->color;
    if(z->left==T->nil){
        x=z->right;
        rb_transplant(T,z,x);
    }else if(z->right==T->nil){
        x=z->left;
        rb_transplant(T,z,x);
    }else{
        y=tree_minimum(T,z->right);
        y_origin_color=y->color;
        x=y->right;
        if(y->parent==z) x->parent=y;//y是被删除节点z的右孩子节点
        else {//y不是被删除节点z的子节点
            rb_transplant(T,y,y->right);
            y->right=z->right;
            y->right->parent=y;
        }
        rb_transplant(T,z,y);
        y->color=z->color;
        y->left=z->left;
        y->left->parent=y;
    }
    if(y_origin_color==BLACK)
        rbtree_delete_fix(T,x);//用y替换了被删除节点的数据，相当于y被删除了，所有要调节y下面的子树满足红黑树要求
}

Node* search(rb_root* T,Type key){
    Node* y=T->root;
    while(y!=T->nil){
        if(y->key==key) return y;
        else if(y->key<key) y=y->right;
        else y=y->left;
    }
    return NULL;
}

void delete_rbtree(rb_root* T,Type key){
    Node* t=search(T,key);
    if(t!=NULL)
        rbtree_delete(T,t);
}

void rbtree_print(rb_root* T,Node* tree,Type key,int dir){
    if(tree!=T->nil){
        if(0==dir)
            printf("%2d(B) is root\n",tree->key);
        else
            printf("%2d(%c) is %2d's %6s child\n",tree->key,tree->color==RED?'R':'B',key,dir==1?"right":"left");
        rbtree_print(T,tree->left,tree->key,-1);
        rbtree_print(T,tree->right,tree->key,1);
    }
}

void print_rbtree(rb_root* root){
    rbtree_print(root,root->root,root->root->key,0);
}

int main()
{
    //int a[]={10,40,30,60,90,70,20,50,80,65};
    int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80,65,66,45,77,99,82,23,55,88,33,47};
    rb_root T;
    T.nil=(Node*)malloc(sizeof(Node));
    T.nil->left=T.nil->right=T.nil->parent=T.nil;
    T.nil->color=BLACK;
    T.root=T.nil;
    for(int i=0;i<sizeof(a)/sizeof(int);i++){
        printf("%d\n",i);
        rb_insert_type(&T,a[i]);
        print_rbtree(&T);
        printf("\n");
    }
    for(int i=5; i<sizeof(a)/sizeof(Type); i++){
		printf("== 删除节点: %d\n", a[i]);
        delete_rbtree(&T, a[i]);
        if (T.root!=NULL)
        {
            printf("== 树的详细信息: \n");
            print_rbtree(&T);
            printf("\n");
        }
    } 
    return 0;
}