＃i nclude <stdio.h> 
＃i nclude <malloc.h> 

typedef char Key; //定義數據域的類型
typedef struct red_black_node *rbptr;//定義指向結點的指針 
enum nodecolor {red, black}; //結點顏色的枚舉類型 

typedef struct red_black_node //定義結點數據結構
{ 
 Key data; //數據
 rbptr lc; //左指針
 rbptr rc; //右指針
 rbptr p; //父指針
 enum nodecolor color; //顏色
} rbnode; 

static rbnode NIL = {0, NULL, NULL, NULL, black}; //定義一個空結點 

rbptr rb_build_tree (rbptr root,Key a[]);//建立紅黑樹 
rbptr minimum (rbptr x);//查最小結點
rbptr maximum (rbptr x); //查最大結點
rbptr predecessor (rbptr x);//查前序 
rbptr successor (rbptr x); //查中序
rbptr rb_search (rbptr x, Key k); //查找一個關鍵字的指針
rbptr left_rotate (rbptr root, rbptr x); //左旋
rbptr right_rotate (rbptr root, rbptr x);//右旋 
rbptr rb_inserc (rbptr root, rbptr z); //插入結點
rbptr rb_inserc_fixup (rbptr root, rbptr z); //插入后調整
rbptr rb_delete (rbptr root, rbptr z); //刪除結點
rbptr rb_delete_fixup (rbptr root, rbptr z); //刪除后調整
rbptr rb_clear_tree (rbptr root);//清除紅黑樹
void rb_print_node (rbptr p); //打印結點
void rb_pre_visit_tree (rbptr root); //紅黑樹先序遍歷
void rb_mid_visit_tree(rbptr root);//紅黑樹中序遍歷
 
rbptr rb_build_tree (rbptr root,Key a[]) //建立紅黑樹
{ 
 int count = 0; 
 rbptr p; 
 while (a[count]!='\0') { //循環，真至讀完全部數據
  p = (struct red_black_node *)malloc (sizeof (struct red_black_node)); //生成一個空結點
  p->data=a[count]; //將新結點填入數據
  p->lc=&NIL; 
  p->rc=&NIL; 
  p->p=&NIL; 
  p->color=red; 
  root=rb_inserc (root, p); //調用插入函數
  count++; 
  } 
  return root; 
}
 
rbptr minimum (rbptr x)//找最小結點 
{ 
 while (x->lc != &NIL)//只要左孩子不是空結點，繼續查找 
 x = x->lc;//指針指向左孩子 
 return x; 
}
 
rbptr maximum (rbptr x)//找最大結點 
{ 
 while (x->rc != &NIL)//只要右孩子不是空結點，繼續查找
 x = x->rc; //指針指向右孩子
 return x; 
}
 
rbptr successor (rbptr x)//找中序后繼 
 { 
 if (x->rc != &NIL)//若右孩子不是空結點 
 return (minimum (x->rc));//找其最小的一個結點 
 while (x->p!= &NIL && x == x->p->rc) //若X的父結點不為空結點且X是其父的右孩子則繼續循環上溯
  x = x->p; 
 return x; 
 }
 
 rbptr predecessor (rbptr x)//找前序后繼 
 { 
 if (x->lc != &NIL)//若左孩子不是空結點 
 return (maximum (x)); //找其最大的一個結點
 while (x->p != &NIL && x == x->p->lc)//若X的父結點不為空結點且X是其父的左孩子則繼續循環上溯 
  x = x->p; 
 return x; 
 }
 
 rbptr rb_search (rbptr x, Key k)//查找一個關鍵字 
 { 
 while (x != &NIL && x->data != k) //X結點不為空且X的數據域不為K，則繼續循環
  if (x->data < k)//若當前結點比關鍵字小
  x = x->rc; //轉向右孩子
  else 
  x = x->lc;//否則轉向左孩子 
  return x; 
 }
 
 rbptr  left_rotate (rbptr root, rbptr x)//左旋 
 { 
 rbptr r = root; //記下根指針
 rbptr y; 
 y = x->rc;//記下X的右孩子 
 x->rc = y->lc;//把X的右孩子指針指向Y的左孩子。（即原X的右孩子的左孩子） 
 y->lc->p = x; //Y左孩子的父指針指向X
 y->p = x->p; //Y的父指針指向X的父結點
 if (x->p == &NIL) 
 r = y;
 else if (x == x->p->lc) 
   x->p->lc = y; 
   else 
   x->p->rc = y; 
 y->lc = x; 
 x->p = y; 
 return r; 
 } 

 rbptr  right_rotate (rbptr root, rbptr x) //右旋
 { 
 rbptr r = root; 
 rbptr y; 
 y = x->lc; 
 x->lc = y->rc; 
 y->rc->p = x; 
 y->p= x->p; 
 if (x->p == &NIL) 
 r = y; 
 else { 
  if (x->p->lc == x) 
  x->p->lc = y; 
  else 
  x->p->rc = y; 
  } 
 y->rc = x; 
 x->p = y; 
 return r; 
 }
 
 rbptr  rb_inserc (rbptr root, rbptr z)//插入數據 
 { 
 rbptr r = root; 
 rbptr x, y; 
 y = &NIL;//y始終是x的父親指針 
 x = root; 
 while (x != &NIL) {//查找插入位置 
  y = x;//y指向x 
  if (z->data < x-> data) 
   x = x->lc; 
  else 
   x = x->rc;
 } 
 z->p = y; 
 if (y == &NIL)//如果紅黑樹為空 
  r = z; 
 else if (z->data < y->data) 
   y->lc = z; 
   else y->rc = z; 
 z->lc = &NIL; 
 z->rc = &NIL; 
 z->color = red;//插入結點涂紅 
 r = rb_inserc_fixup (r, z); //調整
 return r; 
 } 

 rbptr  rb_inserc_fixup (rbptr root, rbptr z) 
 { 
 rbptr r = root; 
 rbptr y; 
 while (z->p->color == red) { 
  if (z->p == z->p->p->lc) { //情況1 ，Z的父親是z祖父的左孩子 
   y = z->p->p->rc; //Y指向Z的叔叔
   if (y->color == red) {//Y如果是紅  
    z->p->color = black;//把Z的父親涂黑  
    y->color = black;//把Y（即Z的叔叔）也涂黑  
    z->p->p->color = red;//把Y的祖父涂紅  
    z = z->p->p;//Z上溯至其祖父  
    } 
   else {  
    if (z == z->p->rc) { //情況2，Z的父親是z祖父的右孩子 
     z = z->p;//Z指向其父親  
     r = left_rotate (r, z);//左旋，變成情況3  
     } 
    z->p->color = black;//情況3，如果Z的父親為黑 
    z->p->p->color = red;//把Z的祖父涂紅 
    r = right_rotate (r, z->p->p);//右旋 
     } 
    } 
    else if (z->p == z->p->p->rc) { 
     y = z->p->p->lc; 
     if (y->color == red) {//情況4
      z->p->color = black; 
      y->color = black; 
      z->p->p->color = red; 
      z = z->p->p; 
      } 
     else { 
      if (z == z->p->lc) { //情況5 
       z = z->p;  
       r = right_rotate (r, z);  
        } 
      z->p->color = black; //情況6
      z->p->p->color = red;  
      r = left_rotate (r, z->p->p); 
       } 
      } 
     } 
   r->color = black; 
   return r; 
 }
 
 rbptr  rb_delete (rbptr root, rbptr z) 
 { 
 rbptr r = root; 
 rbptr x, y; //y是將被刪除的結點
 if (z->lc == &NIL || z->rc == &NIL)//情況2 
  y = z;//Z至少有一個孩子為空 
 else 
  y = successor (z); //Y是Z的中序后繼，變成情況2
 if (y->lc != &NIL)//Y至多有一個非空的孩子 
  x = y->lc;//若Y有一個非空的孩子，則X指向它，否則X為空 
 else 
  x = y->rc;
  x->p = y->p; 
  if (y == r)//如果Y是根 
  r = x;//X變為根 
  else if (y == y->p->lc) 
  y->p->lc = x; 
    else y->p->rc = x; 
  if (y != z)  z->data= y->data;//情況3，將Y中的內容放到Z中 
 if (y->color == black) 
  r = rb_delete_fixup (r, x); 
  free (y); 
 return r; 
 } 

 rbptr  rb_delete_fixup (rbptr root, rbptr z) 
 { 
 rbptr r = root; 
 rbptr w; 
 while (z != r && z->color == black) { //至多調整到根或碰到一個紅色結點
  if (z == z->p->lc) {
   w = z->p->rc;
   if (w->color == red) { 
    w->color = black; 
    z->p->color = red; 
    r = left_rotate (r, z->p); 
    w = z->p->rc; 
    } 
   else if (w->lc->color == black  && w->rc->color == black) {  
    w->color = red; 
    z = z->p; 
    } 
   else { 
    if (w->rc->color == black) {  
    w->lc->color = black; 
    w->color = red; 
    r = right_rotate (r, w); 
    w = z->p->rc; 
    } 
   w->color = z->p->color;  
   w->rc->color = black; 
   z->p->color = black;
   r = left_rotate (r, z->p); 
   z = r; 
    } 
   } 
  else { 
   w = z->p->lc; 
   if (w->color == red) { 
    w->color = black; 
    z->p->color = red; 
    r = right_rotate (r, z->p); 
    w = z->p->lc; 
    } 
   else if (w->lc->color == black  && w->rc->color == black) { 
     w->color = red; 
     z = z->p; 
     } 
   else { 
    if (w->lc->color == black) { 
     w->color = red; 
     w->rc->color = black; 
     r = left_rotate (r, w); 
     w = z->p->lc; 
     } 
    w->color = z->p->color;
    z->p->color = black; 
    w->lc->color = black; 
    r = right_rotate (r, z->p); 
    z = r; 
    } 
   } 
  } 
 z->color = black; 
 return r; 
 } 

 rbptr  rb_clear_tree (rbptr root)//清除一棵指定的紅黑樹，釋放內存。 
 { 
 if (root != &NIL) { 
  root->lc = rb_clear_tree (root->lc); 
  root->rc = rb_clear_tree (root->rc); 
  free (root); 
  root = &NIL;
  } 
 return root; 
 } 
 
 void  rb_print_node (rbptr p)//打印，每行打印五個結點。 
 { static int i=0;
 if (p != &NIL) 
  if (p->color == red){
   if(i%5==0)printf("\n");
   printf ("[%c (紅色)]\t", p->data);
   }
  else {
   if(i%5==0)printf("\n");
   printf ("[%c (黑色)]\t", p->data); 
   }
 i++;
 }
 
 void  rb_pre_visit_tree (rbptr root)//前序遍歷
 { 
 if (root != &NIL) { 
  rb_print_node (root); 
  rb_pre_visit_tree (root->lc); 
  rb_pre_visit_tree (root->rc); 
  } 
 } 

 void rb_mid_visit_tree(rbptr root)//中序遍歷
 { 
 if (root != &NIL) { 
  rb_mid_visit_tree (root->lc); 
  rb_print_node (root);
  rb_mid_visit_tree (root->rc); 
  } 
 } 
 
 int  main () 
 { 
 char a[11]="acfdbihejg\0";
 rbptr root,p,r;
 root=&NIL;
 root=rb_build_tree(root,a);
 printf("\n\n中序遍歷該紅黑樹（原始）：\n");
 rb_mid_visit_tree(root);
 printf("\n\n");
 p=rb_search (root, 'd');
 r=rb_delete (root,p);
 printf("\n\n中序遍歷該紅黑樹（刪除結點d后）：\n");
 rb_mid_visit_tree(root);
 printf("\n\n");
 getch(); 

return 0;
 }