红黑树用来存储单个汉字GBK编码

红黑树用来存储单个汉字GBK编码

红黑树用来存储单个汉字GBK编码：

#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>

#define   RAND   10000
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;
  char  gbk[5]={0};
  if(level>40)
    {
      printf("error\n");
      error_label=1;
      return 100000 ;
    }
  if (!root)
    {
      return  0;
    }
  else
    {
      right= mid_print  (root  ->right,level+1);
      gbk[0]=root->m_data/256;
      gbk[1]=root->m_data%256;
      //      printf("{address=%x color=%s,level=%d ,value=%s}   ",root ,root->m_color==RED?"red":"black",level ,gbk);
      printf("%s%d",gbk,root->m_data);
      //   printf(" %d   ",root->m_data->value);
      left=mid_print (root ->left,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;
  int  word_count;
  int  word_buffer[RAND]={0};

  FILE *fp = NULL;
  char buffer[64] = "";
  uint value = 0;
  char *pvalue = NULL;
  int weight = 0;
  int ikeylen = 0;
  char strFilePath[128] = "";

  char  buf[100]="";
  unsigned char word[100]="\0";
  int  gbk=0;

  init();
  srand(time(NULL));
  node=(wrapdata*)calloc (1  ,sizeof (wrapdata));
  global_node=node;

  getcwd(buf, sizeof(buf)-1);
  sprintf(strFilePath, "%s/%s", buf ,"single.txt");
  fp = fopen(strFilePath, "rt");

  word_count=0;
  while (fgets(buffer, sizeof(buffer) - 1, fp) > 0)
    {

      pvalue = (char *)memchr(buffer, '\t', sizeof(buffer));
      ikeylen = (pvalue - buffer);
      memcpy( word ,buffer ,ikeylen);

      //      printf("add  word  %s ",buffer);
      gbk=word[0] * 256 + word[1];
      insert(node ,gbk);
      word_buffer[word_count++]=gbk;
    }
  fclose(fp);

  while(1)
    {

 

      //     printf("into  insert  mode\n");
      while( node->size< word_count)
 {
   i=rand()%word_count;
   insert  (node ,word_buffer[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==word_count*2/3)
     {
       //       mid_print(node->root,0);
       printf("%d  %d  \n",node->size,depth (node->root));

     }
 
 }
      //      mid_print(node->root,0);     
      //      printf("into  delete  mode\n");
      while( node->size> word_count/2)
 {
   i=rand()%word_count;
   delete  (node ,word_buffer[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==word_count*2/3)
     {
       //       mid_print(node->root,0);
       printf("%d  %d  \n",node->size,depth (node->root));
     }
 
 }
    }
  return  0;
}