因为看内核的时候感觉红黑树挺有意思的，所以利用周末的时间来实现一下玩玩。红黑树的操作主要是插入和删除，而删除的时候需要考虑的情况更多一些。具体的操作就不在这里罗嗦了，百度文库里面有一个比较有好的文章，已经说的很明白了。
在看具体的操作的时候有的人可能感觉有些情况是没有考虑到的（如果没有这种感觉的人很有可能根本没有仔细地想）。但是那些“遗漏”的情况如果存在的话，操作之前的红黑树将违反那几个规则。
写代码的时候很多次因为少考虑情况而导致错误，细节比较多，刚开始rb_node中没有指向父节点的指针，写的快吐血，然后还是加上了。代码具体的含义可以结合文章和注释来看（还是很好理解的）。下面的代码中可能还有没有考虑到的细节，欢迎拍砖。
1 #include
2 #include 3 4 const int RED = 0; 5 const int BLACK = 1; 6 7 struct rb_node{ 8 rb_node* lchild, *rchild, *parent; 9 int key, colour; 10 }; 11 rb_node* root; 12 13 rb_node* get_node(rb_node* parent, int key); 14 void rb_insert(int key); 15 rb_node* rb_search(int key); 16 void rb_delete(int key); 17 rb_node* clock_wise(rb_node* node); 18 rb_node* counter_clock_wise(rb_node* node); 19 void show_rb_tree(rb_node* node); 20 21 rb_node* get_node(rb_node* parent, int key){ 22 rb_node *tmp = (rb_node*)malloc(sizeof(rb_node)); 23 tmp->key = key; 24 tmp->colour = RED; 25 tmp->parent = parent; 26 tmp->lchild = tmp->rchild = NULL; 27 return tmp; 28 } 29 30 rb_node* clock_wise(rb_node* node){ 31 if(node == NULL || node->lchild == NULL) 32 return NULL; 33 34 rb_node *rb_1=node, *rb_2=node->lchild, *rb_3=node->lchild->rchild; 35 if(rb_1->parent != NULL){ 36 if(rb_1->parent->lchild == rb_1) 37 rb_1->parent->lchild = rb_2; 38 else 39 rb_1->parent->rchild = rb_2; 40 }else if(rb_1 == root){ 41 root = rb_2; 42 } 43 rb_2->parent = rb_1->parent; 44 45 rb_1->parent = rb_2; 46 rb_2->rchild = rb_1; 47 48 rb_1->lchild = rb_3; 49 if(rb_3 != NULL)rb_3->parent = rb_1; 50 51 return rb_2; 52 } 53 54 rb_node* counter_clock_wise(rb_node* node){ 55 if(node == NULL || node->rchild == NULL) 56 return NULL; 57 58 rb_node *rb_1=node, *rb_2=node->rchild, *rb_3=node->rchild->lchild; 59 if(rb_1->parent != NULL){ 60 if(rb_1->parent->lchild == rb_1) 61 rb_1->parent->lchild = rb_2; 62 else 63 rb_1->parent->rchild = rb_2; 64 } 65 else if(rb_1 == root){ 66 root = rb_2; 67 } 68 rb_2->parent = rb_1->parent; 69 70 rb_1->parent = rb_2; 71 rb_2->lchild = rb_1; 72 73 rb_1->rchild = rb_3; 74 if(rb_3 != NULL)rb_3->parent = rb_1; 75 76 return rb_2; 77 } 78 79 rb_node* rb_search(int key){ 80 rb_node *p = root; 81 while(p != NULL){ 82 if(key < p->key) 83 p = p->lchild; 84 else if(key > p->key) 85 p = p->rchild; 86 else 87 break; 88 } 89 return p; 90 } 91 92 void rb_insert(int key){ 93 rb_node *p=root, *q=NULL; 94 95 if(root == NULL){ 96 root = get_node(NULL, key); 97 root->colour = BLACK; 98 return; 99 }
100 101 while(p != NULL){
102 q = p;
103 if(key < p->key)
104 p = p->lchild;
105 else if(key > p->key)
106 p = p->rchild;
107 else return;
108 }
109 110 if(key < q->key)
111 q->lchild = get_node(q, key);
112 else
113 q->rchild = get_node(q, key);
114 115 while(q != NULL && q->colour == RED){
116 p = q->parent;//p won't null, or BUG.
117 118 if(p->lchild == q){
119 if(q->rchild != NULL && q->rchild->colour == RED)
120 counter_clock_wise(q); 121 q = clock_wise(p);
122 q->lchild->colour = BLACK;
123 }
124 else{
125 if(q->lchild != NULL && q->lchild->colour == RED)
126 clock_wise(q);
127 q = counter_clock_wise(p);
128 q->rchild->colour = BLACK;
129 }
130 131 q = q->parent;
132 }
133 root->colour = BLACK;
134 }
135 136 void show_rb_tree(rb_node* node){
137 if(node == NULL)
138 return;
139 printf("(%d,%d)\n", node->key, node->colour);
140 if(node->lchild != NULL){
141 printf("[-1]\n");
142 show_rb_tree(node->lchild);
143 }
144 if(node->rchild != NULL){
145 printf("[1]\n");
146 show_rb_tree(node->rchild);
147 }
148 printf("[0]\n");
149 }
150 151 void rb_delete(int key){
152 rb_node *v = rb_search(key), *u, *p, *c, *b;
153 int tmp;
154 if(v == NULL) return;
155 156 u = v;
157 if(v->lchild != NULL && v->rchild != NULL){
158 u = v->rchild;
159 while(u->lchild != NULL){
160 u = u->lchild;
161 }
162 tmp = u->key;
163 u->key = v->key;
164 v->key = tmp;
165 }
166 167 //u is the node to free.
168 if(u->lchild != NULL)
169 c = u->lchild;
170 else 171 c = u->rchild;
172 173 p = u->parent;
174 if(p != NULL){
175 //remove u from rb_tree.
176 if(p->lchild == u)
177 p->lchild = c;
178 else
179 p->rchild = c;
180 }
181 else{
182 //u is root.
183 root = c;
184 free((void*)u);
185 return;
186 }
187 188 //u is not root and u is RED, this will not unbalance.
189 if(u->colour == RED){
190 free((void*)u);
191 return;
192 }
193 194 free((void*)u);
195 u = c;
196 197 //u is the first node to balance.
198 while(u != root){
199 if(u != NULL && u->colour == RED){
200 //if u is RED, change it to BLACK can finsh.
201 u->colour = BLACK;
202 return;
203 }
204 205 if(u == p->lchild)
206 b = p->rchild;
207 else 208 b = p->lchild;
209 210 printf("%d\n", b->key);
211 212 //b is borther of u. b can't be null, or the rb_tree is must not balance.
213 if(b->colour == BLACK){
214 //If b's son is RED, rotate the node.
215 if(b->lchild != NULL && b->lchild->colour == RED){
216 if(u == p->lchild){
217 b = clock_wise(b);
218 b->colour = BLACK;
219 b->rchild->colour = RED;
220 221 p = counter_clock_wise(p);
222 p->colour = p->lchild->colour;
223 p->lchild->colour = BLACK;
224 p->rchild->colour = BLACK;
225 }
226 else{
227 p = clock_wise(p);
228 p->colour = p->rchild->colour;
229 p->rchild->colour = BLACK;
230 p->lchild->colour = BLACK;
231 }
232 233 return;
234 }
235 else if(b->rchild != NULL && b->rchild->colour == RED){
236 if(u == p->rchild){
237 b = counter_clock_wise(b);
238 b->colour = BLACK;
239 b->lchild->colour = RED;
240 241 p = clock_wise(p);
242 p->colour = p->rchild->colour;
243 p->rchild->colour = BLACK;
244 p->lchild->colour = BLACK;
245 }
246 else{
247 p = counter_clock_wise(p);
248 p->colour = p->lchild->colour;
249 p->lchild->colour = BLACK;
250 p->rchild->colour = BLACK;
251 } 252 return;
253 }
254 else{//if b's sons are BLACK, make b RED and move up u.
255 b->colour = RED;
256 u = p;
257 p = u->parent;
258 continue;
259 }
260 }
261 else{
262 if(u == p->lchild){
263 p = counter_clock_wise(p);
264 p->colour = BLACK;
265 p->lchild->colour = RED;
266 p = p->lchild;
267 }
268 else{
269 p = clock_wise(p);
270 p->colour = BLACK;
271 p->rchild->colour = RED;
272 p = p->rchild;
273 }
274 }
275 }
276 root->colour = BLACK;
277 }
278 279 int main(){
280 int i;
281 root = NULL;
282 for(i = 1; i <= 10; i++){ 283 rb_insert(i);
284 }
285 rb_delete(9);
286 rb_delete(3);
287 rb_delete(7);
288 show_rb_tree(root);
289 printf("\n");
290 return 0;
291 }
延伸阅读
最新评论