c - 红黑树帮助 C

Question

我是一个新手，我正在尝试在 CI 中创建一个 rb 树，我设法从 CLRS 对算法和数据结构的介绍中制作了下面的代码伪代码。问题是无论我运行多少次，程序都会崩溃如果它尝试使用其中一个旋转功能。任何建议将不胜感激

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


struct node 
{
  int  data;
  char   color;
  struct node *left;
  struct node *right;
  struct node *parent;
};

struct node *root = NULL;

void leftrotate(struct node* x)
{   printf("\nleft rotate debug \n");
    struct node *y; 
    y=x->right;    // set y
    x->right=y->left;     // turn y's left subtree into x's right subtree
    if (y->left != NULL)  
      y->left->parent = x;
    y->parent = x->parent;  
    if (x->parent==NULL)  // link x's parent to y
        root= y;
    else if ((x->data==x->parent->left->data)&&(x->parent->left!=NULL))
        x->parent->left=y;
    else
        x->parent->right=y;
    y->left=x;            // put x on y's left
    x->parent=y;
    return; 
}

void rightrotate(struct node* y)
{   printf("\n right rotate debug \n");
    struct node *x; 
    x=y->left;     // set x
    y->left =x->right;    // turn x's right subtree into y's left subtree{
    if (x->right != NULL)  
        x->right->parent = y;
    x->parent=y->parent;   // link y's parent to x
    if (y->parent==NULL)  
        root=x;
    else if ((y->data==y->parent->left->data)&&(y->parent->left!=NULL))
       y->parent->left=x;
    else
       y->parent->right=x; 
    x->right=y;         // put y on x's right
    y->parent=x;
    return;
}
void rbinsertfixup(struct node* z)
{
    struct node *y=NULL;
    while ((z->parent!=NULL)&&(z->parent->color=='r'))    //find y's uncle,parent is     red
    {   if((z->parent->parent->left!=NULL)&&(z->parent->data==z->parent->parent->left->data))
          {  if(z->parent->parent->right!=NULL )
               y=z->parent->parent->right;
             if ((y->color=='r')&&(y!=NULL))
             { z->parent->color='b';
               y->color='b';
               z->parent->parent->color='r';
               if(z->parent->parent!=NULL)
                z=z->parent->parent;
             } 
             else 
              { if((z->parent->right!=NULL)&&(z->parent->right->data==z->data))
                 { z=z->parent;
                 leftrotate(z);
                 }
                 z->parent->color='b';
                 z->parent->parent->color='r';
                 rightrotate(z->parent->parent);
              } 
          }
        else
          { if(z->parent->parent->left!=NULL) 
              y=z->parent->parent->left;
            if((y->color=='r')&&(y!=NULL))
             { z->parent->color='b';
               y->color='b';
               z->parent->parent->color='r';
               if(z->parent->parent!=NULL)
                z=z->parent->parent;
             }
            else 
              { if((z->parent->left!=NULL)&&(z->parent->left->data==z->data))
                 { z=z->parent;
                   rightrotate(z);
                 }
                 z->parent->color='b';
                 z->parent->parent->color='r';
                 leftrotate(z->parent->parent);
              } 
          }
      
     }
   root->color='b';       
}

void rbinsert(int key)
{   struct node *x,*y;
    x=root;

    struct node *z=(struct node*) malloc(sizeof(struct node));  // Create new node z
    z->data=key;
    z->left=NULL;
    z->right=NULL;
    z->color='r';  
    if(root==NULL) //Tree has zero entries
    {   root=z;
        z->color='b';
    }
     while (x !=NULL)     // Find where to Insert Z into the  tree
    {
        y = x;
        if (z->data< x->data)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (y ==NULL)
        root = z;
    else if (z->data < y->data)
        y->left  = z;
    else
        y->right = z;

    rbinsertfixup(z);   // Ensure that rbt properties are maintained
    return;
}

      
void printTree(struct node* root)
{
    if (root->left !=NULL)
        printTree(root->left);
    printf("%d %c ", root->data,root->color);
    if (root->right !=NULL)
        printTree(root->right);
}






      
int main(int argc, char* argv[])
{   
    int key;
    char fry;
    fry='a';


    while(fry!='q')
    {
        printf("\n Previous Fry %c \n", fry);
        if (fry!='q')
        {
            printf("\n Give new choice \n");
            fry='a';
            fflush(stdin);
            fry=getchar();
        
            if (fry=='q') printf("\n QUIT \n");
            if (fry=='i')
            {
                printf("\n INSERT \n");
            printf("\n Type in key interger\n");
            scanf("%d",&key);
            rbinsert(key);
            
        }
    
        if (fry=='p')
        {   printf("\n inorderprint \n");
            printTree(root);
        }
        
    }
}
return 0;
}