rbtree.cpp

红黑树的算法源代码,来自那本经典的算法书的,但是有问题,特别是对于复杂的数据链表数据结构有问题,对于整数是可以的

#include <stdio.h> 
#include <malloc.h> 
#include <iostream>
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);//清除红黑树
rbptr rb_above(rbptr root,rbptr z);//返回root中紧靠线段s上面的线段
rbptr rb_below(rbptr root,rbptr z);//返回root中紧靠线段s下面的线段
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); 
  } 
 } 
 rbptr rb_above(rbptr root,rbptr z)//返回root中紧靠线段z上面的线段
 {   rbptr pt;
      pt=root;
     while (pt != &NIL && pt->data != z->data) //X结点不为空且X的数据域不为K，则继续循环
  if (pt->data < z->data)//若当前结点比关键字小
  pt = pt->rc; //转向右孩子
  else 
  pt =pt->lc;//否则转向左孩子 
  return pt->rc；
 }
 rbptr rb_below(rbptr root,rbptr z)//返回root中紧靠线段z下面的线段
 {
	   rbptr pt;
      pt=root;
     while (pt != &NIL && pt->data != z->data) //X结点不为空且X的数据域不为K，则继续循环
  if (pt->data < z->data)//若当前结点比关键字小
  pt = pt->rc; //转向右孩子
  else 
  pt =pt->lc;//否则转向左孩子 
  return pt->lc; 
 }
 void interchange(rbptr root,rbptr z1,rbptr z2)//交换两相邻线段位置
 {key t;
   t=z1.data;z1.data=z2.data;z2.data=t;
 
 }

 int  main () 
 { 
 char a[11]="acfdbihejg";
 rbptr root,p,r,w,q;
 root=&NIL;
 root=rb_build_tree(root,a);
 w=root->lc;w=root->rc;

 q=rb_above(root,w);
 std::cout<<q->data;
 q=rb_below(root,w);
 std::cout<<q->data;
 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");
 


return 0;
 }