hello,
I hope everyone is fine. =)
I have made a red black tree code, with the basic functionalities of insertion, deletion and Search. Presently, I am not getting any error, but when the code reaches the while loop of insertfixup it crashes or whatever ( it pops up a window xstring and points to the following code
int compare(const _Elem *_Ptr) const
{ // compare [0, _Mysize) with [_Ptr, <null>)
_DEBUG_POINTER(_Ptr);
return (compare(0, this->_Mysize, _Ptr, _Traits::length(_Ptr)));
}
Kindly help me with it. I am pasting the code here
Code:#include<iostream> #include<string> using namespace std; class Node { public: string data; Node* left; Node* right; Node* parent; string color; Node() { right = NULL; left = NULL; parent= NULL; } }; class RBT { Node* root; public: RBT() { root = NULL; } void rotateLeft( Node* x ) { Node* y = x->right; x->right= y ->left; y->left->parent= x; y->parent = x->parent; if ( x->parent == NULL) root = y; else if (x == x->parent->left) x->parent->left=y; else x->parent->right = y; y->left = x; x->parent = y; } void rotateRight(Node* x) { Node* y = x->left; x->left= y ->right; y->right->parent= x; y->parent = x->parent; if ( x->parent == NULL) root = y; else if (x == x->parent->left) x->parent->right=y; else x->parent->left = y; y->right=x; x->parent=y; } void insertFixUp(Node* z) { Node* y; //cout<<"Hello"; while( z->parent->color == "RED") { //cout<<"i"; 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; rotateLeft(z); } z->parent->color = "BLACK"; z->parent->parent->color = "RED"; rotateRight(z->parent->parent); } else { z = z->parent; rotateRight(z); } z->parent->color = "BLACK"; z->parent->parent->color = "RED"; rotateLeft(z->parent->parent); } //cout<<"Hello2"; root->color = "BLACK"; } void insert(string data) { Node* z = new Node; z->data = data; Node* y = NULL; Node* x = root; while (x != NULL) { y=x; if (z->data < x->data) x = x->left; else x = x->right; } z->parent = y; if ( y == NULL) root = z; else if (z->data < y->data) y->left = z; else y->right= z; z->left = NULL; z->right = NULL; z->color = "RED"; //z->parent = y; insertFixUp(z); } void inOrder(Node* abc) { if(abc != NULL) { if(abc->left) inOrder(abc->left); cout<<" "<<abc->data<<" "; if( abc->right) inOrder(abc->right); } else return; } void printInOrder() { inOrder(root); } Node* searchDelete(string data) { Node* y=root; Node* x= root; while ( x != NULL ) { if (x->data == data) { return x; } //y=1; break; } if (data < x->data) x= x->left; else x=x->right; } //return y; } void deleteRb(string data) { Node* y; Node* z = searchDelete(data); Node* x; if ( z->left == NULL || z->right == NULL ) y=z; else y = treeSuccessor(z); if (y->left != NULL) x= y->left; else x= y->right; x->parent = y->parent; if ( y->parent == NULL) root = x; else if (y = y->parent->left) y->parent->left = x; else y->parent->right = x; if ( y != z) z->data = y->data; if ( y->color == "BLACK" ) deleteFixUp(x); } void deleteFixUp( Node* x ) { Node* w; while ( x != root && x->color == "BLACK" ) { if ( x = x->parent->left ) { w = x->parent->right; if ( w->color == "RED") { w->color = "RED"; x->parent->color = "RED"; rotateLeft(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"; rotateRight(w); w = x->parent->right; } w->color= x->parent->color; x->parent->color = "BLACK"; w->right->color = "BLACK"; rotateLeft(x->parent); x = root; } else { w->right->color = "BLACK"; w->color = "RED"; rotateLeft(w); w = x->parent->left; w->color = x->parent->color; x->parent->color = "BLACK"; w->left->color = "BLACK"; rotateRight(x->parent); x = root; } } root->color = "BLACK"; } Node* treeMinimum(Node* x) { while (x->left != NULL) x= x->left; return x; } Node* treeSuccessor(Node* x) { if (x->right != NULL) return treeMinimum (x->right); Node* y; y = x->parent; while ( y != NULL) { if ( x == y->right) { x=y; y=y->parent; } return y; } } }; int main() { RBT rbt; Node z; rbt.insert("C"); rbt.insert("A"); rbt.insert("B"); rbt.insert("D"); rbt.printInOrder(); rbt.deleteRb("A"); system("Pause"); return 0; }
