程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 經過自動壓力測試的紅黑樹(刪除功能完備)

經過自動壓力測試的紅黑樹(刪除功能完備)

編輯:關於C

#include  <stdio.h>

#include  <stdlib.h>

 

#define   COUNT   10000

#define   RAND    (4*COUNT)

 

int  error_label=0;

 

 

#pragma  pack(1)

typedef   enum  _color

  {

    RED,

    BLACK

  }color;

 

typedef   struct  _data

{

  int  value;

}data;

typedef  struct  _redblack

{

  color    m_color;

  int   m_data;

  struct  _redblack  *parent;

  struct  _redblack  *left;

  struct  _redblack  *right;

}redblack;

typedef  struct  _wrapredblack

{

  struct  _wrapredblack  *next;

  redblack  real;

}wrapredblack;

typedef  struct  _wrapdata

{

  redblack  *root;

  int  size;

}wrapdata;

#pragma  pack()

 

 

wrapredblack  global[2*RAND];

wrapredblack  *head;

wrapredblack  *tail;

wrapdata  *global_node;

 

 

void  init( )

{

  int  i,j;

  for(i=0;i<RAND-1;i++)

    {

      global[i].next=&global[i+1];

    }

  head=&global[0];

  tail=&global[RAND-1];

}

 

redblack  *mycalloc ( )

{

  redblack  *temp=&head->real;

  head=head->next;

  return  temp;

  //  return (redblack *) calloc (1 ,sizeof (redblack));

}

int checkvalid ( redblack *del,redblack *root)

{

  if(!root)

    {

      return  0;

    }

  else

    {

      if(checkvalid(del,root->left))

 {

   return  1;

 }

      if(checkvalid  (del,root->right))

 {

   return    1;

 }

      if (root==del)

 {

   return  1;

 }

      else

 {

   return  0;

 }

    }

}

void  myfree (redblack  *node)

{

  wrapredblack  *temp = (wrapredblack *)( (int)node-4);

  temp->next=0;

  node->left=node->right=node->parent=0;

  tail->next=temp;

  tail=temp;

 

  if(checkvalid (node,global_node->root))

    {

      exit(0);

    }

 

 

   

  return ;

}

 

int  compare ( int data   ,redblack  *right)

{

  if(data >  right->m_data)

    {

      return  1;

    }

  else    if(data ==  right->m_data)

    {

      return  -1;

    }

  else

    {

      return  0;

    }

}

 

redblack  * newstruct ( int value)

{

  redblack  *newnode;

  newnode=(redblack *)mycalloc ();

  newnode->m_color=RED;

  newnode->m_data =value;

  return  newnode;

}

 

void  rotate_right ( redblack * left ,redblack  *right )

{

 

  right->left=left->right;

  if(left->right)

    {

      left->right->parent=right;

    }

 

  left->right=right;

  left->parent=right->parent;

  if(right->parent)

    {

      if(right->parent->left==right)

 {

   right->parent->left=left;

 }

      else

 {

   right->parent->right=left;

 }

    }

  right->parent=left;

 

}

 

void  rotate_left ( redblack * left ,redblack  *right )

{

  left->right=right->left;

  if (right->left)

    {

      right->left->parent=left;

    }

 

  right->left=left;

  right->parent=left->parent;

  if(left->parent)

    {

      if(left->parent->right==left)

 {

   left->parent->right=right;

 }

      else

 {

   left->parent->left=right;

 }

    }

  left->parent=right;

}

 

int   mid_print (redblack  *root,int level)

{

  int  left,right;

  if(level>40)

    {

      printf("error\n");

      error_label=1;

      return 100000 ;

    }

  if (!root)

    {

      return  0;

    }

  else

    {

      left=mid_print (root ->left,level+1);

      printf("{address=%x color=%s,level=%d ,value=%d}   ",root ,root->m_color==RED?"red":"black",level ,root->m_data);

      //   printf(" %d   ",root->m_data->value);

      right= mid_print  (root  ->right,level+1);

      return  left+right+1;

    }

}

 

int   check (redblack  *root)

{

  int  left,right;

  if (!root)

    {

      return  0;

    }

  else

    {

      left=check (root ->left);

      right= check  (root  ->right);

      if(left||right)

 {

   return  1;

 }

      if(  root->left  && ( root->left->m_data >  root->m_data ||  root->left->parent!=root)  )

 {

   return  1;

 }

      if(  root->right  && ( root->right->m_data <  root->m_data  || root->right->parent!=root))

 {

   return  1;

 }

      else

 {

   return  0;

 }

 

    }

}

 

 

void   left_print (redblack  *root)

{

  if (!root)

    {

      return;

    }

  else

    {

      printf("%d   ",root->m_data);

      left_print (root ->left);

      left_print  (root  ->right);

    }

}

 

 

void   right_print (redblack  *root)

{

  if (!root)

    {

      return;

    }

  else

    {

      right_print (root ->left);

      right_print  (root  ->right);

      printf("%d   ",root->m_data);

    }

}

 

int  depth(redblack  *root)

{

  int  left,right;

  if (!root)

    {

      return 0;

    }

  else

    {

      left=depth(root->left);

      right=depth(root->right);

      return        left>right ? ( left+1):(right+1);

 

    }

}

void  insert_fixup (wrapdata  *node , redblack *newnode)

{

 

  redblack *curnode;

  redblack  *parent;

  redblack  *grandparent;

  redblack *tmp;

  curnode=newnode;

  parent=curnode->parent;

  while(  curnode->m_color==RED  &&   parent ->m_color==RED)

    {

      grandparent=parent->parent;

      if ( curnode == parent->left)

 {

   if (  parent == grandparent->left)

     {

       curnode->m_color=BLACK;

       rotate_right ( parent , grandparent);

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

     }

   else

     {

       //       printf("nothing");

       rotate_right (curnode,  parent );

       tmp=parent;

       parent=curnode;

       curnode=tmp;

 

       curnode->m_color=BLACK;

       rotate_left (grandparent ,parent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

     }

 }

      else

 {

   if (  parent== grandparent->right)

     {

       curnode->m_color=BLACK;

       rotate_left (grandparent,parent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

 

     }

   else

     {

       //       printf("nothing");

       rotate_left (  parent ,curnode);

       tmp=parent;

       parent=curnode;

       curnode=tmp;

 

       curnode->m_color=BLACK;

       rotate_right (parent,grandparent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

     }

 }

    }

}

redblack  * find(redblack *root ,int  data)

{

  if (! root)

    {

      return  NULL;

    }

  else

    {

      if ( data ==  root->m_data)

 {

   return  root;

 }

      else      if  (  data >  root->m_data)

 {

   return  find (root ->right ,data);

 }

      else

 {

   return  find (root->left ,data );

 }

    }

}

 

redblack  * next (redblack  * mostleft)

{

  //   if

  if(! mostleft->left)

    {

      return  mostleft;

    }

  else

    {

      return   next ( mostleft->left);

    }

}

 

void  delete_fixup (wrapdata *node,  redblack *curnode ,int mode)

{

  redblack  *parent;

  redblack  *uncle;

  redblack  *uncle_left;

  redblack  *uncle_right;

 

  while(1)

    {

      if (curnode->m_color==RED)

 {

   curnode->m_color=BLACK;

   parent=curnode->parent;

   if(!parent)

     {

       node->root=curnode;

     }

   return ;

 }

      else

 {

   parent=curnode->parent;

   if(!parent)

     {

       node->root=curnode;

       return ;

     }

   if(0==mode)

     {

 

       uncle=parent->right;

       if(!uncle)

  {

    return ;

  }

 

       if (uncle->m_color== RED)

  {

    uncle->m_color=BLACK;

    parent->m_color=RED;

    rotate_left (parent,uncle );

    if (!uncle->parent)

      {

        node->root=uncle;

      }

 

  }

       else

  {

    uncle_left=uncle->left;

    uncle_right=uncle->right;

    if(  (!uncle_left ||  uncle_left->m_color==BLACK )

         &&

         (!uncle_right  ||  uncle_right->m_color==BLACK))

      {

        uncle->m_color=RED;

        curnode=parent;

 

 

      }

    else

      {

        if( !uncle_right || (uncle_right&& uncle_right->m_color==RED))

   {

     uncle->m_color=parent->m_color;

     parent->m_color=BLACK;

     if(uncle_right)

       {

         uncle_right->m_color=BLACK;

       }

 

     rotate_left( parent,uncle);

     if (!uncle->parent)

       {

         node->root=uncle;

       }

     return ;

 

   }

        else

   {

     uncle_left->m_color=BLACK;

     uncle->m_color=RED;

     rotate_right(uncle_left,uncle);

 

     uncle=parent->right;

     uncle->right=uncle->right;

 

     uncle->m_color=parent->m_color;

     parent->m_color=BLACK;

                          uncle_right->m_color=BLACK;

 

     rotate_left( parent,uncle);

     if (!uncle->parent)

       {

         node->root=uncle;

       }

     return ;

   }

 

      }

 

  }

 

     }

   else

     {

       uncle=parent->left;

       if(!uncle)

  {

    return ;

  }

 

       if (uncle->m_color== RED)

  {

    uncle->m_color=BLACK;

    parent->m_color=RED;

    rotate_right (uncle ,parent);

    if (!uncle->parent)

      {

        node->root=uncle;

      }

 

  }

       else

  {

    uncle_left=uncle->left;

    uncle_right=uncle->right;

    if(  (!uncle_left ||  uncle_left->m_color==BLACK )

         &&

         (!uncle_right  ||  uncle_right->m_color==BLACK))

      {

        uncle->m_color=RED;

        curnode=parent;

 

      }

    else

      {

        if( !uncle_left || ( uncle_left &&  uncle_left->m_color==RED))

   {

     uncle->m_color=parent->m_color;

     parent->m_color=BLACK;

     if(uncle_left)

       {

         uncle_left->m_color=BLACK;

       }

 

     rotate_right( uncle , parent);

     if (!uncle->parent)

       {

         node->root=uncle;

       }

     return ;

 

   }

        else

   {

     uncle->m_color=RED;

     uncle_right->m_color=BLACK;

     rotate_left(  uncle ,uncle_right);

 

     uncle=parent->left;

     uncle_left=uncle->left;

 

     uncle->m_color=parent->m_color;

     parent->m_color=BLACK;

                          uncle_left->m_color=BLACK;

 

     rotate_right( uncle , parent);

     if (!uncle->parent)

       {

         node->root=uncle;

       }

     return ;

   }

      }

 

  }

     }

 }

    }

}

 

void  delete  (wrapdata  *node ,int  data)

{

  redblack  * drop;

  redblack  *suc;

  redblack  *curnode;

  int  value;

  int  mode;

 

 

  if ( drop=find ( node->root ,data))

    {

      printf("will  delete   %d \n",data);

      if(!drop->left  &&  !drop->right )

 {

   if (!drop->parent)

     {

       myfree(drop);

       node->root=0;

      

     }

   else

     {

       if (drop->parent->left==drop)

  {

    drop->parent->left=0;

  }

       else

  {

    drop->parent->right=0;

  }

       myfree  (drop);

     }

 }

      else  if (!drop->right )

 {

   if(!drop ->parent)

     {

       node->root=drop->left;

     }

   else

     {

       if (drop->parent->left==drop)

  {

    drop->parent->left=drop->left;

    mode=0;

  }

       else

  {

    drop->parent->right=drop->left;

    mode=1;

  }

     }

 

   curnode=drop->left;

   curnode->parent=drop->parent;

   myfree  (drop);

   delete_fixup (node, curnode,mode);

 

 }

      else

 {

   suc=next ( drop->right);

   value=drop->m_data;

   drop->m_data=suc->m_data;

   suc->m_data=value;

 

   if(suc->parent->left==suc)

     {

       mode=0;

     }

   else

     {

       mode=1;

     }

 

   if(!suc->right)

     {

 

       if(0==mode)

  {

    suc->parent->left=0;

  }

       else

  {

    suc->parent->right=0;

  }

 

       myfree(suc);

     }

   else

     {

       if(0==mode)

  {

    suc->parent->left=suc->right;

  }

       else

  {

    suc->parent->right=suc->right;

  }

 

       curnode=suc->right;

       curnode->parent=suc->parent;

       myfree(suc);

       delete_fixup  (node ,curnode,mode);

 

     }

 

 }

      node->size--;

    }

  else

    {

    }

  node->root->m_color=BLACK;

}

 

void  insert  ( wrapdata  *node , int  data )

{

  redblack  *newnode;

  redblack  *curnode;

  int  relation;

 

  node->size++;

  newnode=newstruct (data);

  printf("will  insert %x  %d \n",newnode,data);

 

  if ( ! node->root)

    {

      node->root= newnode;

    }

  else

    {

      curnode=node->root;

      while(1)

 {

   relation=compare(data,curnode);

   if(relation==-1)

     {

       node->size--;

       myfree(newnode);

       return ;

     }

   else

     {     

       if (   relation==1)

  {

    if (!curnode->right)

      {

        curnode->right=newnode;

        newnode->parent=curnode;

 

        break;

      }

    else

      {

        curnode=curnode->right;

      }

  }

       else

  {

    if (!curnode->left)

      {

        curnode->left=newnode;

        newnode->parent=curnode;

        break;

      }

    else

      {

        curnode=curnode->left;

      }

  }

     }

 }

      insert_fixup ( node , newnode);

    }

  node->root->m_color=BLACK;

}

 

 

int  main()

{

  int  i;

  wrapdata  *node;

  data  *newdata;

  int  count;

 

  init();

  srand(time(NULL));

  node=(wrapdata*)calloc (1  ,sizeof (wrapdata));

  global_node=node;

 

  /*

    int  value[]={12,24,25,9,4,91,2,100,98,95,93,96,99,120,13};

    //    int  value[]={12,24,25,9,4,91,2};

    node=(wrapdata*)calloc (1  ,sizeof (wrapdata));

    for (i=0;i<sizeof (value)/sizeof(int );i++)

    {

    insert (node ,value[i]);

    }

 

    printf("%d  \n",depth (node->root));

    mid_print (node->root,0);

    printf("\n");

 

 

    while(1)

    {

    printf("into  delete  mode\n");

    while( scanf("%d",&i)  &&  i)

    {

    delete  (node ,i);

    printf("%d  \n",depth (node->root));

    mid_print (node->root,0);

    printf("\n");

    }

 

    printf("into  insert  mode\n");

    while( scanf("%d",&i)  &&  i)

    {

    insert  (node ,i);

    printf("%d  \n",depth (node->root));

    mid_print (node->root,0);

    printf("\n");

    }

 

    }

  */

 

  while(1)

    {

      //     printf("into  insert  mode\n");

      while( node->size< COUNT)

 {

   i=rand()%RAND;

   insert  (node ,i);

   count=check(node->root);

   if(count)

     {

       //       printf("\ncheck  error\n");

       mid_print(node->root,0);

       return ;

     }

   count=mid_print (node->root,0);

   if(count!=node->size)

     {

       //      printf("\n  %d  %d  \n",count ,node->size);

       return ;

     }

   if(error_label)

     {

       return ;

     }

 

   if(node->size==COUNT*2/3)

     {

       printf("%d  %d  \n",node->size,depth (node->root));

     }

 

 }

     

      //      printf("into  delete  mode\n");

      while( node->size> COUNT/2)

 {

   i=rand()%RAND;

   delete  (node ,i);

   count=check(node->root);

   if(count)

     {

       //      printf("\ncheck  error\n");

       return ;

     }

   count=mid_print (node->root,0);

   if(count!=node->size)

     {

       //       printf("\n delete error  %d  %d  \n",count ,node->size);

       return ;

     }

   if(error_label)

     {

       return ;

     }

   if(node->size==COUNT*2/3)

     {

       printf("%d  %d  \n",node->size,depth (node->root));

     }

 

 }

    }

  return  0;

}

摘自 chenbingchenbing的專欄

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved