001 红黑树(二)之 C语言的实现(2)

  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("%2d(B) is root\n", tree->key);
694        else                // tree是分支节点
695            printf("%2d(%s) is %2d's %6s child\n", 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}