Red Black Tree Book実装（SIGSEGVが発生しました）

Question

私は大学の書籍に基づいてタイトルアルゴリズムの実装を書こうとしています。私は最も重要な機能を書いたが、私はプログラムのクラッシュに終わる。ラインでGDBのオンラインデバッガポイント91 Program received signal SIGSEGV, Segmentation fault. 0x0000000000400ac4 in RB_Insert (T=0x0, k=5) at main.c:90 90 while((X != root) && (X->up->color == 'R')){

5私はそう、私は声明X != rootがそれを停止しないとSIGSEGVが

を印刷している理由私はここに全体のコードを貼り付けます疑問を挿入しようとしている最初の値です。

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

struct node{ 
    int key; 
    char color; 
    struct node *up; 
    struct node *left; 
    struct node *right; 
}*root; 


void in_order_tree_walk(struct node *X){ 
    if(X!=NULL){ 
     in_order_tree_walk(X->left); 
     printf("%d %c\n", X->key, X->color); 
     in_order_tree_walk(X->right); 
    } 
} 

struct node* tree_search(struct node *X, int k){ 
    if(X==NULL || k==X->key) 
     return X; 
    if(k<X->key) 
     return tree_search(X->left, k); 
    else 
     return tree_search(X->right, k); 
} 

struct node* tmp_node(int k){ 
    struct node *tmp = (struct node*)malloc(sizeof *root); 
    tmp->up = NULL; 
    tmp->left = NULL; 
    tmp->right = NULL; 
    tmp->key = k; 
    tmp->color = 'R'; 
    return tmp; 
} 

void tree_insert(struct node *T, struct node *Z){ 
    if (T == NULL){ 
     T = Z; 
     return; 
    } 
    else{ 
     if (Z->key < T->key){ 
     tree_insert(T->left, Z); 
     T->left->up = T; 
    } 
    else if (Z->key > T->key){ 
     tree_insert(T->right,Z); 
     T->right->up = T; 
    } 
    } 
} 

void left_rotate(struct node *X){ 
    struct node *Y = X->right; 
    X->right = Y->left; 
    if(Y->left != NULL) 
     Y->left->up = X; 
    Y->up = X->up; 
    if(X->up == NULL) 
     root = Y; 
    else if(X == X->up->left) 
     X->up->left = Y; 
     else X->up->right = Y; 
    Y->left = X; 
    X->up = Y; 
} 

void right_rotate(struct node *X){ 
    struct node *Y = X->left; 
    X->left = Y->right; 
    if(Y->right != NULL) 
     Y->right->up = X; 
    Y->up = X->up; 
    if(X->up == NULL) 
     root = Y; 
    else if(X == X->up->left) 
     X->up->left = Y; 
    else X->up->right = Y; 
    Y->right = X; 
    X->up = Y; 
} 

void RB_Insert(struct node *T, int k){ 
    struct node *X = tmp_node(k); 
    tree_insert(T, X); 
    X->color = 'R'; 
    while(X != root && X->up->color == 'R'){ 
     if(X->up = X->up->up->left){ 
      struct node *Y = X->up->up->right; 
      if(Y->color == 'R'){ 
       X->up->color = 'B'; 
       Y->color = 'B'; 
       X->up->up->color = 'R'; 
       X = X->up->up; 
      } 
      else{ 
       if (X == X->up->right){ 
       X = X->up; 
       left_rotate(X); 

       } 
       X->up->color = 'B'; 
       X->up->up->color = 'R'; 
       right_rotate(X->up->up); 
      } 
     } 
     else{ 
      struct node *Y = X->up->up->left; 
      if(Y->color == 'R'){ 
       X->up->color = 'B'; 
       Y->color = 'B'; 
       X->up->up->color = 'R'; 
       X = X->up->up; 
      } 
      else{ 
       if (X == X->up->left){ 
       X = X->up; 
       right_rotate(X); 
       } 
       X->up->color = 'B'; 
       X->up->up->color = 'R'; 
       left_rotate(X->up->up); 
      } 
     } 
    } 
    root->color = 'B'; 
} 

int main(){ 

    root = NULL; 
    int T[] = {5,26,17,8,9,30,10,1,23}; 
    int i; 
    for(i=0; i<9; i++){ 
     printf("%d", T[i]); 
     RB_Insert(root, T[i]); 
    } 
    printf("\n"); 
    in_order_tree_walk(root); 

    return 0; 
} 

Answer 1

私は

struct node *Y = NULL; 
    struct node *X = root; 
    while(X != NULL) 
    { 
     Y = X; 
     if(Z->key < X->key) X=X->left; 
     else X=X->right; 
    } 
    Z->up = Y; 
    if(Y == NULL) 
    root = Z; 
    else if(Z->key < Y->key) Y->left = Z; 
    else Y->right = Z; 

にtree_insertを変更し、if文の行114でに追加if(Y != NULL && Y->color == 'R'){これは今すぐうまくいきます