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