红黑树的实现文件(rbtree.c):
代码语言：javascript复制 1/**
2 * C语言实现的红黑树(Red Black Tree)
3 *
4 * @author skywang
5 * @date 2013/11/18
6 */
7#include <stdio.h>
8#include <stdlib.h>
9#include "rbtree.h"
10#define rb_parent(r) ((r)->parent)
11#define rb_color(r) ((r)->color)
12#define rb_is_red(r) ((r)->color==RED)
13#define rb_is_black(r) ((r)->color==BLACK)
14#define rb_set_black(r) do { (r)->color = BLACK; } while (0)
15#define rb_set_red(r) do { (r)->color = RED; } while (0)
16#define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)
17#define rb_set_color(r,c) do { (r)->color = (c) } while (0)
18/*
19 * 创建红黑树，返回"红黑树的根"！
20 */
21RBRoot* create_rbtree()
22{
23 RBRoot *root = (RBRoot *)malloc(sizeof(RBRoot));
24 root->node = NULL;
25
26 return root;
27}
28
29/*
30 * 前序遍历"红黑树"
31 */
32static void preorder(RBTree tree)
33{
34 if(tree != NULL)
35 {
36 printf("%d ", tree->key);
37 preorder(tree->left);
38 preorder(tree->right);
39 }
40}
41void preorder_rbtree(RBRoot *root)
42{
43 if (root)
44 preorder(root->node);
45}
46
47/*
48 * 中序遍历"红黑树"
49 */
50static void inorder(RBTree tree)
51{
52 if(tree != NULL)
53 {
54 inorder(tree->left);
55 printf("%d ", tree->key);
56 inorder(tree->right);
57 }
58}
59
60void inorder_rbtree(RBRoot *root)
61{
62 if (root)
63 inorder(root->node);
64}
65
66/*
67 * 后序遍历"红黑树"
68 */
69static void postorder(RBTree tree)
70{
71 if(tree != NULL)
72 {
73 postorder(tree->left);
74 postorder(tree->right);
75 printf("%d ", tree->key);
76 }
77}
78
79void postorder_rbtree(RBRoot *root)
80{
81 if (root)
82 postorder(root->node);
83}
84
85/*
86 * (递归实现)查找"红黑树x"中键值为key的节点
87 */
88static Node* search(RBTree x, Type key)
89{
90 if (x==NULL || x->key==key)
91 return x;
92
93 if (key < x->key)
94 return search(x->left, key);
95 else
96 return search(x->right, key);
97}
98int rbtree_search(RBRoot *root, Type key)
99{
100 if (root)
101 return search(root->node, key)? 0 : -1;
102}
103
104/*
105 * (非递归实现)查找"红黑树x"中键值为key的节点
106 */
107static Node* iterative_search(RBTree x, Type key)
108{
109 while ((x!=NULL) && (x->key!=key))
110 {
111 if (key < x->key)
112 x = x->left;
113 else
114 x = x->right;
115 }
116 return x;
117}
118
119int iterative_rbtree_search(RBRoot *root, Type key)
120{
121 if (root)
122 return iterative_search(root->node, key) ? 0 : -1;
123}
124
125/*
126 * 查找最小结点：返回tree为根结点的红黑树的最小结点。
127 */
128static Node* minimum(RBTree tree)
129{
130 if (tree == NULL)
131 return NULL;
132 while(tree->left != NULL)
133 tree = tree->left;
134 return tree;
135}
136
137int rbtree_minimum(RBRoot *root, int *val)
138{
139 Node *node;
140 if (root)
141 node = minimum(root->node);
142 if (node == NULL)
143 return -1;
144 *val = node->key;
145 return 0;
146}
147
148/*
149 * 查找最大结点：返回tree为根结点的红黑树的最大结点。
150 */
151static Node* maximum(RBTree tree)
152{
153 if (tree == NULL)
154 return NULL;
155 while(tree->right != NULL)
156 tree = tree->right;
157 return tree;
158}
159
160int rbtree_maximum(RBRoot *root, int *val)
161{
162 Node *node;
163 if (root)
164 node = maximum(root->node);
165 if (node == NULL)
166 return -1;
167 *val = node->key;
168 return 0;
169}
170
171/*
172 * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
173 */
174static Node* rbtree_successor(RBTree x)
175{
176 // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
177 if (x->right != NULL)
178 return minimum(x->right);
179 // 如果x没有右孩子。则x有以下两种可能：
180 // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
181 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
182 Node* y = x->parent;
183 while ((y!=NULL) && (x==y->right))
184 {
185 x = y;
186 y = y->parent;
187 }
188 return y;
189}
190
191/*
192 * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
193 */
194static Node* rbtree_predecessor(RBTree x)
195{
196 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
197 if (x->left != NULL)
198 return maximum(x->left);
199 // 如果x没有左孩子。则x有以下两种可能：
200 // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
201 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
202 Node* y = x->parent;
203 while ((y!=NULL) && (x==y->left))
204 {
205 x = y;
206 y = y->parent;
207 }
208 return y;
209}
210
211/*
212 * 对红黑树的节点(x)进行左旋转
213 *
214 * 左旋示意图(对节点x进行左旋)：
215 * px px
216 * / /
217 * x y
218 * / --(左旋)--> / #
219 * lx y x ry
220 * / /
221 * ly ry lx ly
222 *
223 *
224 */
225static void rbtree_left_rotate(RBRoot *root, Node *x)
226{
227 // 设置x的右孩子为y
228 Node *y = x->right;
229 // 将 “y的左孩子” 设为 “x的右孩子”；
230 // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
231 x->right = y->left;
232 if (y->left != NULL)
233 y->left->parent = x;
234 // 将 “x的父亲” 设为 “y的父亲”
235 y->parent = x->parent;
236
237 if (x->parent == NULL)
238 {
239 //tree = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
240 root->node = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
241 }
242 else
243 {
244 if (x->parent->left == x)
245 x->parent->left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
246 else
247 x->parent->right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
248 }
249
250 // 将 “x” 设为 “y的左孩子”
251 y->left = x;
252 // 将 “x的父节点” 设为 “y”
253 x->parent = y;
254}
255
256/*
257 * 对红黑树的节点(y)进行右旋转
258 *
259 * 右旋示意图(对节点y进行左旋)：
260 * py py
261 * / /
262 * y x
263 * / --(右旋)--> / #
264 * x ry lx y
265 * / / #
266 * lx rx rx ry
267 *
268 */
269static void rbtree_right_rotate(RBRoot *root, Node *y)
270{
271 // 设置x是当前节点的左孩子。
272 Node *x = y->left;
273 // 将 “x的右孩子” 设为 “y的左孩子”；
274 // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
275 y->left = x->right;
276 if (x->right != NULL)
277 x->right->parent = y;
278 // 将 “y的父亲” 设为 “x的父亲”
279 x->parent = y->parent;
280
281 if (y->parent == NULL)
282 {
283 //tree = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
284 root->node = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
285 }
286 else
287 {
288 if (y == y->parent->right)
289 y->parent->right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
290 else
291 y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
292 }
293 // 将 “y” 设为 “x的右孩子”
294 x->right = y;
295 // 将 “y的父节点” 设为 “x”
296 y->parent = x;
297}
298
299/*
300 * 红黑树插入修正函数
301 *
302 * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
303 * 目的是将它重新塑造成一颗红黑树。
304 *
305 * 参数说明：
306 * root 红黑树的根
307 * node 插入的结点 // 对应《算法导论》中的z
308 */
309static void rbtree_insert_fixup(RBRoot *root, Node *node)
310{
311 Node *parent, *gparent;
312 // 若“父节点存在，并且父节点的颜色是红色”
313 while ((parent = rb_parent(node)) && rb_is_red(parent))
314 {
315 gparent = rb_parent(parent);
316 //若“父节点”是“祖父节点的左孩子”
317 if (parent == gparent->left)
318 {
319 // Case 1条件：叔叔节点是红色
320 {
321 Node *uncle = gparent->right;
322 if (uncle && rb_is_red(uncle))
323 {
324 rb_set_black(uncle);
325 rb_set_black(parent);
326 rb_set_red(gparent);
327 node = gparent;
328 continue;
329 }
330 }
331 // Case 2条件：叔叔是黑色，且当前节点是右孩子
332 if (parent->right == node)
333 {
334 Node *tmp;
335 rbtree_left_rotate(root, parent);
336 tmp = parent;
337 parent = node;
338 node = tmp;
339 }
340 // Case 3条件：叔叔是黑色，且当前节点是左孩子。
341 rb_set_black(parent);
342 rb_set_red(gparent);
343 rbtree_right_rotate(root, gparent);
344 }
345 else//若“z的父节点”是“z的祖父节点的右孩子”
346 {
347 // Case 1条件：叔叔节点是红色
348 {
349 Node *uncle = gparent->left;
350 if (uncle && rb_is_red(uncle))
351 {
352 rb_set_black(uncle);
353 rb_set_black(parent);
354 rb_set_red(gparent);
355 node = gparent;
356 continue;
357 }
358 }
359 // Case 2条件：叔叔是黑色，且当前节点是左孩子
360 if (parent->left == node)
361 {
362 Node *tmp;
363 rbtree_right_rotate(root, parent);
364 tmp = parent;
365 parent = node;
366 node = tmp;
367 }
368 // Case 3条件：叔叔是黑色，且当前节点是右孩子。
369 rb_set_black(parent);
370 rb_set_red(gparent);
371 rbtree_left_rotate(root, gparent);
372 }
373 }
374 // 将根节点设为黑色
375 rb_set_black(root->node);
376}
377
378/*
379 * 添加节点：将节点(node)插入到红黑树中
380 *
381 * 参数说明：
382 * root 红黑树的根
383 * node 插入的结点 // 对应《算法导论》中的z
384 */
385static void rbtree_insert(RBRoot *root, Node *node)
386{
387 Node *y = NULL;
388 Node *x = root->node;
389 // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
390 while (x != NULL)
391 {
392 y = x;
393 if (node->key < x->key)
394 x = x->left;
395 else
396 x = x->right;
397 }
398 rb_parent(node) = y;
399 if (y != NULL)
400 {
401 if (node->key < y->key)
402 y->left = node; // 情况2：若“node所包含的值” < “y所包含的值”，则将node设为“y的左孩子”
403 else
404 y->right = node; // 情况3：(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子”
405 }
406 else
407 {
408 root->node = node; // 情况1：若y是空节点，则将node设为根
409 }
410 // 2. 设置节点的颜色为红色
411 node->color = RED;
412 // 3. 将它重新修正为一颗二叉查找树
413 rbtree_insert_fixup(root, node);
414}
415
416/*
417 * 创建结点
418 *
419 * 参数说明：
420 * key 是键值。
421 * parent 是父结点。
422 * left 是左孩子。
423 * right 是右孩子。
424 */
425static Node* create_rbtree_node(Type key, Node *parent, Node *left, Node* right)
426{
427 Node* p;
428 if ((p = (Node *)malloc(sizeof(Node))) == NULL)
429 return NULL;
430 p->key = key;
431 p->left = left;
432 p->right = right;
433 p->parent = parent;
434 p->color = BLACK; // 默认为黑色
435 return p;
436}
437
438/*
439 * 新建结点(节点键值为key)，并将其插入到红黑树中
440 *
441 * 参数说明：
442 * root 红黑树的根
443 * key 插入结点的键值
444 * 返回值：
445 * 0，插入成功
446 * -1，插入失败
447 */
448int insert_rbtree(RBRoot *root, Type key)
449{
450 Node *node; // 新建结点
451 // 不允许插入相同键值的节点。
452 // (若想允许插入相同键值的节点，注释掉下面两句话即可！)
453 if (search(root->node, key) != NULL)
454 return -1;
455 // 如果新建结点失败，则返回。
456 if ((node=create_rbtree_node(key, NULL, NULL, NULL)) == NULL)
457 return -1;
458 rbtree_insert(root, node);
459 return 0;
460}
461
462/*
463 * 红黑树删除修正函数
464 *
465 * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
466 * 目的是将它重新塑造成一颗红黑树。
467 *
468 * 参数说明：
469 * root 红黑树的根
470 * node 待修正的节点
471 */
472static void rbtree_delete_fixup(RBRoot *root, Node *node, Node *parent)
473{
474 Node *other;
475
476 while ((!node || rb_is_black(node)) && node != root->node)
477 {
478 if (parent->left == node)
479 {
480 other = parent->right;
481 if (rb_is_red(other))
482 {
483 // Case 1: x的兄弟w是红色的
484 rb_set_black(other);
485 rb_set_red(parent);
486 rbtree_left_rotate(root, parent);
487 other = parent->right;
488 }
489 if ((!other->left || rb_is_black(other->left)) &&
490 (!other->right || rb_is_black(other->right)))
491 {
492 // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
493 rb_set_red(other);
494 node = parent;
495 parent = rb_parent(node);
496 }
497 else
498 {
499 if (!other->right || rb_is_black(other->right))
500 {
501 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
502 rb_set_black(other->left);
503 rb_set_red(other);
504 rbtree_right_rotate(root, other);
505 other = parent->right;
506 }
507 // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
508 rb_set_color(other, rb_color(parent));
509 rb_set_black(parent);
510 rb_set_black(other->right);
511 rbtree_left_rotate(root, parent);
512 node = root->node;
513 break;
514 }
515 }
516 else
517 {
518 other = parent->left;
519 if (rb_is_red(other))
520 {
521 // Case 1: x的兄弟w是红色的
522 rb_set_black(other);
523 rb_set_red(parent);
524 rbtree_right_rotate(root, parent);
525 other = parent->left;
526 }
527 if ((!other->left || rb_is_black(other->left)) &&
528 (!other->right || rb_is_black(other->right)))
529 {
530 // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
531 rb_set_red(other);
532 node = parent;
533 parent = rb_parent(node);
534 }
535 else
536 {
537 if (!other->left || rb_is_black(other->left))
538 {
539 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
540 rb_set_black(other->right);
541 rb_set_red(other);
542 rbtree_left_rotate(root, other);
543 other = parent->left;
544 }
545 // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
546 rb_set_color(other, rb_color(parent));
547 rb_set_black(parent);
548 rb_set_black(other->left);
549 rbtree_right_rotate(root, parent);
550 node = root->node;
551 break;
552 }
553 }
554 }
555 if (node)
556 rb_set_black(node);
557}
558
559/*
560 * 删除结点
561 *
562 * 参数说明：
563 * tree 红黑树的根结点
564 * node 删除的结点
565 */
566void rbtree_delete(RBRoot *root, Node *node)
567{
568 Node *child, *parent;
569 int color;
570 // 被删除节点的"左右孩子都不为空"的情况。
571 if ( (node->left!=NULL) && (node->right!=NULL) )
572 {
573 // 被删节点的后继节点。(称为"取代节点")
574 // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
575 Node *replace = node;
576 // 获取后继节点
577 replace = replace->right;
578 while (replace->left != NULL)
579 replace = replace->left;
580 // "node节点"不是根节点(只有根节点不存在父节点)
581 if (rb_parent(node))
582 {
583 if (rb_parent(node)->left == node)
584 rb_parent(node)->left = replace;
585 else
586 rb_parent(node)->right = replace;
587 }
588 else
589 // "node节点"是根节点，更新根节点。
590 root->node = replace;
591 // child是"取代节点"的右孩子，也是需要"调整的节点"。
592 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
593 child = replace->right;
594 parent = rb_parent(replace);
595 // 保存"取代节点"的颜色
596 color = rb_color(replace);
597 // "被删除节点"是"它的后继节点的父节点"
598 if (parent == node)
599 {
600 parent = replace;
601 }
602 else
603 {
604 // child不为空
605 if (child)
606 rb_set_parent(child, parent);
607 parent->left = child;
608 replace->right = node->right;
609 rb_set_parent(node->right, replace);
610 }
611 replace->parent = node->parent;
612 replace->color = node->color;
613 replace->left = node->left;
614 node->left->parent = replace;
615 if (color == BLACK)
616 rbtree_delete_fixup(root, child, parent);
617 free(node);
618 return ;
619 }
620 if (node->left !=NULL)
621 child = node->left;
622 else
623 child = node->right;
624 parent = node->parent;
625 // 保存"取代节点"的颜色
626 color = node->color;
627 if (child)
628 child->parent = parent;
629 // "node节点"不是根节点
630 if (parent)
631 {
632 if (parent->left == node)
633 parent->left = child;
634 else
635 parent->right = child;
636 }
637 else
638 root->node = child;
639 if (color == BLACK)
640 rbtree_delete_fixup(root, child, parent);
641 free(node);
642}
643
644/*
645 * 删除键值为key的结点
646 *
647 * 参数说明：
648 * tree 红黑树的根结点
649 * key 键值
650 */
651void delete_rbtree(RBRoot *root, Type key)
652{
653 Node *z, *node;
654 if ((z = search(root->node, key)) != NULL)
655 rbtree_delete(root, z);
656}
657
658/*
659 * 销毁红黑树
660 */
661static void rbtree_destroy(RBTree tree)
662{
663 if (tree==NULL)
664 return ;
665 if (tree->left != NULL)
666 rbtree_destroy(tree->left);
667 if (tree->right != NULL)
668 rbtree_destroy(tree->right);
669 free(tree);
670}
671
672void destroy_rbtree(RBRoot *root)
673{
674 if (root != NULL)
675 rbtree_destroy(root->node);
676 free(root);
677}
678
679/*
680 * 打印"红黑树"
681 *
682 * tree -- 红黑树的节点
683 * key -- 节点的键值
684 * direction -- 0，表示该节点是根节点;
685 * -1，表示该节点是它的父结点的左孩子;
686 * 1，表示该节点是它的父结点的右孩子。
687 */
688static void rbtree_print(RBTree tree, Type key, int direction)
689{
690 if(tree != NULL)
691 {
692 if(direction==0) // tree是根节点
693 printf("-(B) is rootn", tree->key);
694 else // tree是分支节点
695 printf("-(%s) is -'s %6s childn", tree->key, rb_is_red(tree)?"R":"B", key, direction==1?"right" : "left");
696 rbtree_print(tree->left, tree->key, -1);
697 rbtree_print(tree->right,tree->key, 1);
698 }
699}
700
701void print_rbtree(RBRoot *root)
702{
703 if (root!=NULL && root->node!=NULL)
704 rbtree_print(root->node, root->node->key, 0);
705}文章来源： http://www.cnblogs.com/skywang12345/p/3624177.html
