Red Black Tree en C

Question

Je suis en train de mettre en œuvre l'arbre rouge noir en C. Pour référence, je me sers CLRS.

Mais quand je lance le code que je reçois "Segmentation fault (core dumped)" message d'erreur.

Je ne peux pas comprendre ce qui ne va pas dans mon code alors, quelqu'un pourrait-il me dire ce qui ne va pas dans mon code?

Le problème semble être dans la fonction rb_insert_fixup(), mais je ne sais pas ce qui ne va pas en elle.

code

#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

J'ai écrit le mauvais code. Après l'avoir écrit de nouveau à partir de zéro (en utilisant CLRS) et en incluant le nœud sentinelle cette fois, tout va bien. La fonction rb_delete_fixup() est la suivante. Les changements sont en interne if-else. De même, nous devons changer l'if-else interne de rb_insert_fixup. C'était une erreur de ne pas écrire le code correct du pseudo-code.

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; 
}