recursion - Segmentation fault implementing Red Black tree -
this first question on stack overflow!
i have implement red black tree reason getting segmentation fault when running code. i've been through thousand times , still can't seem able figure out went wrong. else can pick i've missed.
the program reads words text file , attempts insert each of words rb tree. i've written similar program uses string comparative operators insert binary search tree, don't think that's problem.
#include <iostream> #include <string> #include <fstream> using namespace std; enum color {red,black}; struct node{ enum color color; string value; node *leftchild,*rightchild,*parent; }; class rbt{ private: string filename; node* root = null; int readfile(){//read file , insert each word bst ifstream file; file.open (filename.c_str()); if (!file.is_open()) return 1; string word; while (file >> word){// each word in file insert(word); } return 0; } void left_rotate(node* x){ node* y = x->rightchild; x->rightchild = y->leftchild; if(y->leftchild != null) y->leftchild->parent = x; y->parent = x->parent; if(x->parent == null) root = y; else if(x->parent->leftchild == x) x->parent->leftchild = y; else x->parent->rightchild = y; y->leftchild = x; x->parent = y; } void right_rotate(node* y){ node* x = y->leftchild; y->leftchild = x->rightchild; if(x->rightchild != null) x->rightchild->parent = y; x->parent = y->parent; if(y->parent == null) root = x; else if(y->parent->leftchild == y) y->parent->leftchild = x; else y->parent->rightchild = x; x->rightchild = y; y->parent = x; } void insert_fix(node* z){ while (z->parent->color == red) { if (z->parent == z->parent->parent->leftchild) { node* y = z->parent->parent->rightchild; 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->rightchild){ z = z->parent; left_rotate(z); } z->parent->color = black; z->parent->parent->color = red; right_rotate(z->parent->parent); } } else{ node* y = z->parent->parent->leftchild; 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->leftchild){ z = z->parent; right_rotate(z); } z->parent->color = black; z->parent->parent->color = red; left_rotate(z->parent->parent); } } } (root)->color = black; } void tree_insert(node* z){ node* y = null; node* x = root; while(x != null) { y = x; if(z->value < x->value){ x = x->leftchild; } else if (z->value > x->value){ x = x->rightchild; } else{ return; } } z->parent = y; if(y == null) root = z; else if(z->value < y->value) y->leftchild = z; else y->rightchild = z; z->leftchild = null; z->rightchild = null; z->color = red; insert_fix(z); } public: rbt(string _filename); void insert(string s){ node* strnode = new node; strnode->value=s; strnode->leftchild=null; strnode->rightchild=null; strnode->parent=null; tree_insert(strnode); } }; rbt::rbt(string _filename){ filename = _filename; root = new node; readfile(); } int main(){ rbt rbt1 ("words.txt"); }
Comments
Post a Comment