Brains


on Algorithm, Red Black Tree

Red Black Tree

本文参考算法导论书籍以及一些博客,实现了红黑树的插入删除算法。

简介

红黑树这个算法,以后可能会再次遇到,我就在此记录一下。这个算法使用的C语言实现的。

红黑树的原理讲解

我是通过参考枫叶博主关于对红黑树讲解,以及算法导论这本书大致了解了红黑树的实现细节。具体参见红黑树删除操作

红黑树的C实现


  1 #include <\stdio.h>     //  因为markdown过滤性质加了一个'\',include应直接包含stdio.h
  2 #include <\stdlib.h>
  3
  4 typedef enum Color
  5 {
  6         RED = 0,
  7         BLACK = 1
  8 }Color;
  9
 10 typedef struct Node
 11 {
 12         int value;
 13         Color color;
 14         struct Node * parent;
 15         struct Node * left;
 16         struct Node * right;
 17 }Node, *Tree;
 18
 19 Node * nil = NULL;        // is a leaf node
 20 char color[2][6] = { {"RED"}, {"BLACK"} } ;
 21
 22 void left_rotate( Tree * T, Node * x )  // x's right subtree will be x's new parent
 23 {
 24         if( x->right != nil )
 25         {
 26                 Node * y = x->right;
 27
 28                 x->right = y->left;
 29
 30                 if( y->left != nil )      // is not a leaf
 31                 {
 32                         y->left->parent = x;
 33                 }
 34
 35                 y->parent = x->parent;
 36
 37                 if( x->parent == nil )   // x is root
 38                 {
 39                         *T = y;
 40                 }
 41                 else
 42                 {
 43                         if( x == x->parent->left )
 44                         {
 45                                 x->parent->left = y;
 46                         }
 47                         else
 48                         {
 49                                 x->parent->right = y;
 50                         }
 51                 }
 52
 53                 y->left = x;
 54                 x->parent = y;
 55         }
 56         else
 57         {
 58                 printf("can not execute left rotate: right child is nil !\n");
 59         }
 60 }
 61
 62 void right_rotate( Tree * T, Node * x )  // x's left subtree will be x's new parent
 63 {
 64         if( x->left != nil )
 65         {
 66                 Node * y = x->left;
 67
 68                 x->left = y->right;
 69
 70                 if( y->right != nil )
 71                 {
 72                         y->right->parent = x;
 73                 }
 74
 75                 y->parent = x->parent;
 76
 77                 if( x->parent == nil )
 78                 {
 79                         *T = y;
 80                 }
 81                 else
 82                 {
 83                         if( x == x->parent->left )
 84                         {
 85                                 x->parent->left = y;
 86                         }
 87                         else
 88                         {
 89                                 x->parent->right = y;
 90                         }
 91
 92                 }
 93
 94                 y->right = x;
 95                 x->parent = y;
 96         }
 97         else
 98         {
 99                 printf("can not execute right rotate : left child is nil !\n");
100         }
101 }
102
103 void insert_fix_up( Tree * T, Node * z )
104 {
105         Node * y;
106
107         while( z->parent->color == RED )
108         {
109                 if( z->parent->parent->left == z->parent )       // z's parent is a left subtree
110                 {
111                         y = z->parent->parent->right;
112
113                         if( y->color == RED )                    // case 1
114                         {
115                                 y->color = BLACK;
116                                 z->parent->color = BLACK;
117                                 z->parent->parent->color = RED;
118                                 z = z->parent->parent;
119                         }
120                         else if( z == z->parent->right )         // case 2
121                         {
122                                 z = z->parent;
123
124                                 left_rotate( T, z );
125                         }
126                         else                                    // case 3
127                         {
128                                 z->parent->color = BLACK;
129                                 z->parent->parent->color = RED;
130
131                                 right_rotate( T, z->parent->parent );
132                         }
133                 }
134                 else
135                 {
136                         y = z->parent->parent->left;
137
138                         if( y->color == RED )                    // case 1
139                         {
140                                 y->color = BLACK;
141                                 z->parent->color = BLACK;
142                                 z->parent->parent->color = RED;
143                                 z = z->parent->parent;
144                         }
145                         else if( z == z->parent->left )         // case 2
146                         {
147                                 z = z->parent;
148
149                                 right_rotate( T, z );
150                         }
151                         else                                    // case 3
152                         {
153                                 z->parent->color = BLACK;
154                                 z->parent->parent->color = RED;
155
156                                 left_rotate( T, z->parent->parent );
157                         }
158                 }
159         }
160
161         (*T)->color = BLACK;
162 }
163
164 void insert_node( Tree * T, int value )
165 {
166         if( (*T) == NULL )                                //
167         {
168                 (*T) = ( Tree )malloc( sizeof(Node) );
169                 nil = (Node *)malloc( sizeof(Node) );
170
171                 nil->color = BLACK;     // nil init NULL as a globle var ...
172
173                 (*T)->left = nil;
174                 (*T)->right = nil;
175                 (*T)->parent = nil;
176                 (*T)->value = value;
177                 (*T)->color = BLACK;
178         }
179         else
180         {
181                 Node * x = *T;
182                 Node * parent = nil;     // save x's parent
183
184                 while( x != nil )
185                 {
186                         parent = x;
187
188                         if( value < x->value )
189                         {
190                                 x = x->left;
191                         }
192                         else if( value > x->value )
193                         {
194                                 x = x->right;
195                         }
196                         else
197                         {
198                                 printf("value = %d node has existed !\n", value );
199
200                                 return ;
201                         }
202                 }
203
204                 x = ( Node * )malloc(sizeof(Node));
205
206                 x->color = RED;
207                 x->left = nil;
208                 x->right = nil;
209                 x->parent = parent;
210                 x->value = value;
211
212                 if( value < parent->value )
213                 {
214                         parent->left = x;
215                 }
216                 else
217                 {
218                         parent->right = x;
219                 }
220
221                 insert_fix_up( T, x );
222         }
223 }
224
225 void delete_fix_up( Tree * T, Node * x )
226 {
227         while( x != *T && x->color == BLACK )   // only fix up black node
228         {
229                 if( x == x->parent->left )
230                 {
231                         Node * w = x->parent->right;
232
233                         if( w->color == RED )                   // case 1
234                         {
235                                 w->color = BLACK;
236                                 x->parent->color = RED;
237
238                                 left_rotate( T, x->parent );
239
240                                 w = x->parent->right;
241                         }
242
243                         if( w->left->color == BLACK && w->right->color == BLACK )  // case 2
244                         {
245                                 w->color = RED;
246                                 x = x->parent;
247                         }
248
249                         else if( w->right->color == BLACK )      // case 3
250                         {
251                                 w->left->color = BLACK;
252                                 w->color = RED;
253
254                                 right_rotate( T, w );
255
256                                 w = x->parent->right;
257                         }
258
259                         else                                    // case4
260                         {
261                                 w->color = x->parent->color;
262                                 x->parent->color = BLACK;
263                                 w->right->color = BLACK;
264
265                                 left_rotate( T, x->parent );
266
267                                 x = *T;
268                         }
269                 }
270
271                 else
272                 {
273                         Node * w = x->parent->left;
274
275                         if( w->color == RED )                   // case 1
276                         {
277                                 w->color = BLACK;
278                                 x->parent->color = RED;
279
280                                 right_rotate( T, x->parent );
281
282                                 w = x->parent->left;
283                         }
284
285                         if( w->left->color == BLACK && w->right->color == BLACK )  // case 2
286                         {
287                                 w->color = RED;
288                                 x = x->parent;
289                         }
290
291                         else if( w->left->color == BLACK )      // case 3
292                         {
293                                 w->right->color = BLACK;
294                                 w->color = RED;
295
296                                 left_rotate( T, w );
297
298                                 w = x->parent->left;
299                         }
300
301                         else                                    // case4
302                         {
303                                 w->color = x->parent->color;
304                                 x->parent->color = BLACK;
305                                 w->left->color = BLACK;
306
307                                 right_rotate( T, x->parent );
308
309                                 x = *T;
310                         }
311                 }
312         }
313
314         x->color = BLACK;
315 }
316
317 Node * get_node( Tree T, int value )
318 {
319         while( T != NULL && T != nil )
320         {
321                 if( value == T->value ) return T;
322
323                 if( value > T->value )
324                 {
325                         T = T->right;
326                 }
327                 else
328                 {
329                         T = T->left;
330                 }
331         }
332
333         printf("Not find this node < value : %d >\n", value );
334
335         return NULL;
336 }
337
338 Node * successor( Tree T, Node * x )
339 {
340         if( x->right != nil )           // find the successor from the right subtree
341         {
342                 Node * q = x->right;
343                 Node * p = x->right;
344
345                 while( p->left != nil )
346                 {
347                         q = p->left;
348                         p = p->left;
349                 }
350
351                 return q;
352         }
353         else
354         {
355                 Node * parent = x->parent;
356
357                 while( parent != nil && x->value > parent->value )
358                 {
359                         x = x->parent;
360                         parent = parent->parent;
361                 }
362
363                 return parent;
364         }
365 }
366
367 void delete_node( Tree * T, Node * z )
368 {
369         Node * y;         //  we delete this node
370         Node * x;         //  the child of deleted node
371
372         if( z->left == nil || z->right == nil )
373         {
374                 y = z;
375         }
376         else
377         {
378                 y = successor( *T, z );       // y don't have right child
379         }
380
381         if( y->left != nil )
382         {
383                 x = y->left;
384         }
385         else
386         {
387                 x = y->right;
388         }
389
390         x->parent = y->parent;
391
392         if( y->parent == nil )
393         {
394                 *T = x;
395         }
396         else
397         {
398                 if( y == y->parent->left )
399                 {
400                         y->parent->left = x;
401                 }
402                 else
403                 {
404                         y->parent->right = x;
405                 }
406         }
407
408         if( y != z )
409         {
410                 z->value = y->value;
411         }
412
413         if( y->color == BLACK ) delete_fix_up( T, x );
414
415         free( y );
416 }
417
418 void mid_traversal( Tree T )
419 {
420         if( T != NULL && T != nil )
421         {
422                 mid_traversal( T->left );
423
424                 printf("value: %d color: %s\n", T->value, color[T->color] );
425
426                 mid_traversal( T->right );
427         }
428 }
429
430 int main()
431 {
432         Tree t = NULL;
433
434         insert_node( &t, 41 );
435         insert_node( &t, 38 );
436         insert_node( &t, 31 );
437         insert_node( &t, 12 );
438         insert_node( &t, 19 );
439         insert_node( &t, 8 );
440
441         printf("\n-------------orignal tree ------------\n");
442         mid_traversal( t );
443
444         printf("\n-------delete value = 8 node----------\n");
445         delete_node( &t, get_node( t, 8 ) );
446         mid_traversal( t );
447
448         printf("\n-------delete value = 12 node----------\n");
449         delete_node( &t, get_node( t, 12 ) );
450         mid_traversal( t );
451
452         printf("\n-------delete value = 19 node----------\n");
453         delete_node( &t, get_node( t, 19 ) );
454         mid_traversal( t );
455
456         printf("\n-------delete value = 31 node----------\n");
457         delete_node( &t, get_node( t, 31 ) );
458         mid_traversal( t );
459
460
461         printf("\n-------delete value = 38 node----------\n");
462         delete_node( &t, get_node( t, 38 ) );
463         mid_traversal( t );
464
465         printf("\n-------delete value = 41 node----------\n");
466         delete_node( &t, get_node( t, 41 ) );
467         mid_traversal( t );
468
469         return 0;
470
471 }

运行效果

运行结果

最后

这个算法写的比较仓促,没有考虑优化方面的事情。这个算法是参考这位博主,虽然他写的中有一些错误,但给我提供许多思路。再次感谢以上两位博主。

comments powered by Disqus

纸上得来终觉浅,绝知此事要躬行~