Help -- Red Black Tree

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

---

I'm guessing that means you are following a null pointer. For instance, if z is the root of the tree, then z->parent is NULL, meaning z->parent->color can't happen.

Look at the code I have wrote, though it is in C, can give you clue what is wrong.

SourceForge.net Repository - [clibutils] Contents of /src/c_rb.c

@avinashdongre - stop digging up old threads just to spam your site!