赤い黒い木がC

Question

私は赤い黒の木をCで実装しようとしています。参照のために私はCLRSを使用しています。

しかし、コードを実行すると、「セグメンテーションフォルト（コアダンプされた）」というエラーメッセージが表示されます。

私のコードで何が間違っているのか分からないので、誰かが私のコードで何が間違っているのか教えていただけますか？

問題は機能rb_insert_fixup()にあるようですが、何が問題なのかはわかりません。

私は、コードが間違って書かれている

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

//constants 
#define RED 0 
#define BLACK 1 

struct node 
{ 
    int key; 
    struct node *left; 
    struct node *right; 
    struct node *parent; 
    int color; 
}; 

struct node *rb_insert(struct node *tree, struct node *z); 

struct node *rb_insert_fixup(struct node *tree, struct node *z); 

struct node *left_rotate(struct node *t, struct node *x); 

struct node *right_rotate(struct node *t, struct node *x); 

struct node *create_node(int key); 

int main() 
{ 
    struct node *tree = NULL; 
    struct node *new; 

    new = create_node(5); 
    tree = rb_insert(tree, new); 

    new = create_node(15); 
    tree = rb_insert(tree, new); 

    new = create_node(4); 
    tree = rb_insert(tree, new); 

    new = create_node(14); 
    tree = rb_insert(tree, new); 
    printf("inserting 14\n"); 

    printf("%d %d\n%d %d\n", (tree->left)->key, (tree->left)->color, ((tree->right)->left)->key, ((tree->right)->left)->color); 

    return 0; 
} 

struct node *rb_insert_fixup(struct node *tree, struct node *z) 
{ 
    struct node *y = NULL; 

    printf("fixup \n"); 

    while (z->parent != NULL && (z->parent)->color == RED) 
    { 
     printf("while\n"); 

     if ((z->parent)->parent != NULL && printf("if condition %d\n", (((z->parent)->parent)->left)->color) && z->parent == ((z->parent)->parent)->left) 
     { 
      printf("start if\n"); 

      y = ((z->parent)->parent)->right; 

      if (y->color == RED) 
      { 
       (z->parent)->color = BLACK; 
       y->color = BLACK; 
       ((z->parent)->parent)->color = RED; 
       z = (z->parent)->parent; 
      } 

      else if (z == (z->parent)->right) 
      { 
       z = z->parent; 
       tree = left_rotate(tree, z); 
      } 

      (z->parent)->color = BLACK; 
      ((z->parent)->parent)->color = RED; 
      tree = right_rotate(tree, ((z->parent)->parent)); 

      printf("End if\n"); 
     } 

     else 
     { 
      y = ((z->parent)->parent)->left; 

      if (y->color == RED) 
      { 
       (z->parent)->color = BLACK; 
       y->color = BLACK; 
       ((z->parent)->parent)->color = RED; 
       z = (z->parent)->parent; 
      } 

      else if (z == (z->parent)->left) 
      { 
       z = z->parent; 
       tree = right_rotate(tree, z); 
      } 

      (z->parent)->color = BLACK; 
      ((z->parent)->parent)->color = RED; 
      tree = left_rotate(tree, ((z->parent)->parent)); 

      printf("End else\n"); 
     } 

     printf("End while\n"); 
    } 

    tree->color = BLACK; 

    return tree; 
} 

struct node *rb_insert(struct node *tree, struct node *z) 
{ 
    struct node *y = NULL; 
    struct node *x = tree; 

    while (x != NULL) 
    { 
     y = x; 

     if (z->key < x->key) 
     { 
      x = x->left; 
     } 

     else 
     { 
      x = x->right; 
     } 
    } 

    z->parent = y; 

    if (y == NULL) 
    { 
     tree = z; 
    } 

    else if (z->key < y->key) 
    { 
     y->left = z; 
    } 

    else 
    { 
     y->right = z; 
    } 

    z->left = NULL; 
    z->right = NULL; 
    z->color = RED; 

    tree = rb_insert_fixup(tree, z); 
    //printf("bye insert\n"); 

    return tree; 
} 

struct node *right_rotate(struct node *t, struct node *x) 
{ 
    struct node *y = x->left; 
    x->left = y->right; 

    if (y->right != NULL) 
    { 
     (y->right)->parent = x; 
    } 

    y->parent = x->parent; 

    if (x->parent == NULL) 
    { 
     t = y; 
    } 

    else if (x == (x->parent)->left) 
    { 
     (x->parent)->left = y; 
    } 

    else 
    { 
     (x->parent)->right = y; 
    } 

    y->right = x; 
    x->parent = y; 

    return t; 
} 

struct node *left_rotate(struct node *t, struct node *x) 
{ 
    struct node *y = x->right; 
    x->right = y->left; 

    if (y->left != NULL) 
    { 
     (y->left)->parent = x; 
    } 

    y->parent = x->parent; 

    if (x->parent == NULL) 
    { 
     t = y; 
    } 

    else if (x == (x->parent)->left) 
    { 
     (x->parent)->left = y; 
    } 

    else 
    { 
     (x->parent)->right = y; 
    } 

    y->left = x; 
    x->parent = y; 

    return t; 
} 

struct node *create_node(int key) 
{ 
    struct node *new = malloc(sizeof(struct node)); 

    if (new == NULL) 
    { 
     fprintf(stderr, "Malloc failed to create a new node\n"); 
     exit(EXIT_FAILURE); 
    } 

    else 
    { 
     new->key = key; 
     new->left = NULL; 
     new->right = NULL; 
     new->parent = NULL; 
     new->color = BLACK; 
    } 
} 

Answer 1

コード。今回はもう一度（CLRSを使用して）それを書いて、今度はセンティナルノードを含めて、すべてが問題ありません。 rb_delete_fixup（）関数は次のとおりです。変更は内側のif-elseにあります。同様に、rb_insert_fixupの内部if-elseを変更する必要があります。擬似コードから正しいコードを書かないのは大失敗でした。

Node *rb_delete_fixup(Node *tree, Node *tree_nil, Node *x) 
{ 


Node *w; 

while (x != tree && x->color == BLACK) 
{ 
    if (x == x->parent->left) 
    { 
     w = x->parent->right; 

     if (w->color == RED) 
     { 
      w->color = BLACK; 
      x->parent->color = RED; 
      tree = left_rotate(tree, tree_nil, x->parent); 
      w = x->parent->right; 
     } 

     if (w->left->color == BLACK && w->right->color == BLACK) 
     { 
      w->color = RED; 
      x = x->parent; 
     } 

     else 
     { 
      if (w->right->color == BLACK) 
      { 
       w->left->color = BLACK; 
       w->color = RED; 
       tree = right_rotate(tree, tree_nil, w); 
       w = x->parent->right; 
      } 

      w->color = x->parent->color; 
      x->parent->color = BLACK; 
      w->right->color = BLACK; 
      tree = left_rotate(tree, tree_nil, x->parent); 
      x = tree; 
     } 
    } 

    else 
    { 
     w = x->parent->left; 

     if (w->color == RED) 
     { 
      w->color = BLACK; 
      x->parent->color = RED; 
      tree = right_rotate(tree, tree_nil, x->parent); 
      w = x->parent->left; 
     } 

     if (w->left->color == BLACK && w->right->color == BLACK) 
     { 
      w->color = RED; 
      x = x->parent; 
     } 

     else 
     { 
      if (w->left->color == BLACK) 
      { 
       w->right->color = BLACK; 
       w->color = RED; 
       tree = left_rotate(tree, tree_nil, w); 
       w = x->parent->left; 
      } 

      w->color = x->parent->color; 
      x->parent->color = BLACK; 
      w->left->color = BLACK; 
      tree = right_rotate(tree, tree_nil, x->parent); 
      x = tree; 
     } 
    } 
} 

x->color = BLACK; 
}