紅黑樹書的實現（SIGSEGV發生）

我試圖根據我的大學書籍來編寫標題算法的實現。我寫了最重要的功能，但最終導致程序崩潰。在線路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')){紅黑樹書的實現（SIGSEGV發生）

5 GDB調試器在線點是第一個值，我試圖插入，所以我不知道爲什麼聲明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; 
}

來源

2017-02-25 Jędrzej

是'if（X-> up = X-> up-> up-> left）{'真的你想要做什麼？ '='是賦值，'=='比較值。你的編譯器會警告你，甚至在線編譯器也會這樣做：http://ideone.com/NGGaL4 – mch

C通過值**傳遞所有函數參數**。因此你的'root'將始終保持爲NULL。這從GDB消息中也很明顯。 –

@mch是啊，這是我的錯，一個錯字，但問題仍然是一樣的 –

我改變tree_insert到

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;

，並添加if語句在114行if(Y != NULL && Y->color == 'R'){它現在正常工作

來源

2017-02-25 14:09:57

紅黑樹書的實現（SIGSEGV發生）

回答

相關問題