c - Segmentation Fault in a Simple Red-Black Tree -
i'm trying build simple red-black tree in c. unfortunately, have encountered segmentation fault i'm not sure how fix. i've included code below , marked line fault occurring.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #define red 1 #define black 0 typedef struct rbnode { char key[50]; int color; struct rbnode *left; struct rbnode *right; struct rbnode *parent; } rbnode; typedef struct rbtree { struct rbnode *root; struct rbnode *nil; } rbtree; void inorderprint(rbtree*, rbnode*); void insertrb(rbtree*, rbnode*); void insertrbfixup(rbtree*, rbnode*); void leftrotate(rbtree*, rbnode*); void rightrotate(rbtree*, rbnode*); int count; int main (int argc, char* argv[]) { rbtree *tree = malloc(sizeof(rbtree)); tree->nil = malloc(sizeof(rbnode)); tree->nil->color = black; tree->root = null; tree->nil->left = tree->root; tree->nil->right = tree->root; rbnode *curr = null; curr = malloc(sizeof(rbnode)); strcpy(curr->key, "cat"); insertrb(tree, curr); strcpy(curr->key, "hat"); insertrb(tree, curr); strcpy(curr->key, "bit"); insertrb(tree, curr); strcpy(curr->key, "car"); insertrb(tree, curr); strcpy(curr->key, "map"); insertrb(tree, curr); inorderprint(tree, tree->root); return 1; } void inorderprint(rbtree* tree, rbnode *node) { if ((node != null) && (node != tree->nil)) { inorderprint(tree, node->left); printf("%s\n", node->key); inorderprint(tree, node->right); } } void leftrotate(rbtree *tree, rbnode *x) { struct rbnode *y = null; y = x->right; x->right = y->left; if (y->left != tree->nil) { y->left->parent = x; //segmentation fault occurs here } y->parent = x->parent; if (x->parent == tree->nil) { tree->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rightrotate(rbtree *tree, rbnode *x) { rbnode *y = x->left; x->left = y->right; if (y->right != tree->nil) { y->right->parent = x; } y->parent = x->parent; if (x->parent == tree->nil) { tree->root = y; } else if (x == x->parent->right) { x->parent->right = y; } else { x->parent->left = y; } y->right = x; x->parent = y; } void insertrb(rbtree *tree, rbnode *z) { rbnode *y = tree->nil; rbnode *x = tree->root; while ((x != tree->nil) && (x != null)) { y = x; if (strcmp(z->key, x->key) < 0) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == tree->nil) { tree->root = z; } else if (strcmp(z->key, y->key) < 0) { y->left = z; } else { y->right = z; } z->left = tree->nil; z->right = tree->nil; z->color = red; insertrbfixup(tree, z); } void insertrbfixup(rbtree *tree, rbnode *z) { rbnode *y = null; while (z->parent->color == red) { if (z->parent == z->parent->parent->left) { 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; leftrotate(tree, z); } else { z->parent->color = black; z->parent->parent->color = red; rightrotate(tree, z->parent->parent); } } 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; rightrotate(tree, z); } else { z->parent->color = black; z->parent->parent->color = red; leftrotate(tree, z->parent->parent); } } } tree->root->color = black; } i think might have how initialized red-black tree in main(), i'm not sure , i've tried many different other ways initialize it.
do of guys know i'm going wrong?
in
if (y->left != tree->nil) { y->left->parent = x; //segmentation fault occurs here } y->left can null.
leftrotate need check null pointers
Comments
Post a Comment