PROGRAM FOR REDBLACK TREE USING C++

#include<iostream>
using namespace std;
class RedBlackNode {
         public:
           int key;
           RedBlackNode *left;
           RedBlackNode *right;
           RedBlackNode *parent;
           char color;
           RedBlackNode (int data,RedBlackNode *leftc=NULL,RedBlackNode *rightc=NULL,RedBlackNode *prnt=NULL)
            {
                key=data;
                left=leftc;
                right=rightc;
                parent=prnt;
            };
class RedBlackTree
{
    public:
    RedBlackNode *root;
    RedBlackTree()
    {
        root=NULL;
    }
    void Left_Rotate(RedBlackNode *x);
    void Right_Rotate(RedBlackNode *x);
    void RB_Insert(RedBlackNode *z);
    void Insert(int inp);
    void RB_Insert_Fixup(RedBlackNode *z);
    RedBlackNode* RB_Delete(RedBlackNode *z);
    void RB_Delete_Fixup(RedBlackNode *x);
    RedBlackNode* Tree_Successor(RedBlackNode *x);
    RedBlackNode* RB_Search(int val);
};

void RedBlackTree::Left_Rotate(RedBlackNode *x)
{
    RedBlackNode *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 RedBlackTree::Right_Rotate(RedBlackNode *x)
{
    RedBlackNode *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->right) {
        x->parent->right=y;
    }
    else x->parent->left=y;
    y->right=x;
    x->parent=y;
}
void RedBlackTree::RB_Insert_Fixup(RedBlackNode *z)
{
    while (z->parent->color=='R')
    {
        if (z->parent == z->parent->parent->left) {
            RedBlackNode *y=z->parent->parent->right;
            if (y->color=='R') {
                z->parent->color='B';
                y->color='B';
                z->parent->parent->color='R';
                z=z->parent->parent;
            }
            else if (z==z->parent->right) {
                z=z->parent;
                Left_Rotate(z);
            }
            z->parent->color='B';
            z->parent->parent->color='R';
            Right_Rotate(z->parent->parent);
        }
        else
        {
            RedBlackNode *y=z->parent->parent->left;
            if (y->color=='R') {
                z->parent->color='B';
                y->color='B';
                z->parent->parent->color='R';
                z=z->parent->parent;
            }
            else if (z==z->parent->left) {
                z=z->parent;
                Right_Rotate(z);
            }
            z->parent->color='B';
            z->parent->parent->color='R';
            Left_Rotate(z->parent->parent);
        }
    }
    root->color='B';
}

void RedBlackTree::RB_Insert(RedBlackNode *z)
{
    RedBlackNode *y=NULL;
    RedBlackNode *x=root;
    while (x!=NULL) {
        y=x;
        if (z->key<x->key)
            x=x->right;
        else x=x->right;
    }
    z->parent=y;
    if (y==NULL)
        root=z;
    else if (z->key<y->key)
        y->left=z;
    else y->right=z;
    z->left= NULL;
    z->right= NULL;
    z->color='R';
    RB_Insert_Fixup(z);
}
void RedBlackTree::Insert(int inp)
{
    RedBlackNode *z=new RedBlackNode(inp);
    RB_Insert(z);
}
RedBlackNode* RedBlackTree::RB_Delete(RedBlackNode* z)
{    RedBlackNode *y, *x;
    if ((z->left==NULL) || (z->right==NULL))
        y=z;
    else y=Tree_Successor(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->key=y->key;
    if (y->color=='B')
        RB_Delete_Fixup(x);
    return y;
}
void RedBlackTree::RB_Delete_Fixup(RedBlackNode* x)
{
    RedBlackNode *w;
     while ((x!=root) && (x->color=1))
    {
        if (x==x->parent->left) {
            w=x->parent->right;
            if (w->color=='R') {
                w->color='B';
                x->parent->color='R';
                Left_Rotate(x->parent);
                w=x->parent->right;
            }
            if ((w->left->color=='B') && (w->right->color=='B')) {
                w->color=0;
                x=x->parent;
            }
            else if (w->right->color=='B') {
                w->left->color='B';
                w->color='R';
                Right_Rotate(w);
                w=x->parent->right;
            }
            w->color=x->parent->color;
            x->parent->color='B';
            w->right->color='B';
            Left_Rotate(x->parent);
            x=root;
        }
        else {
            w=x->parent->left;
            if (w->color=='R') {
                w->color='B';
                x->parent->color='R';
                Right_Rotate(x->parent);
                w=x->parent->left;
            }
            if ((w->right->color=='B') && (w->left->color=='B')) {
                w->color='R';
                x=x->parent;
            }
            else if (w->left->color=='B'){
                w->right->color=1;
                w->color='R';
                Left_Rotate(w);
                w=x->parent->left;
            }
            w->color=x->parent->color;
            x->parent->color='B';
            w->left->color='B';
            Right_Rotate(x->parent);
            x=root;
        }
    }
}
RedBlackNode* RedBlackTree::Tree_Successor(RedBlackNode *x)
{
    if (x->right!=NULL)
    {
        while (x->left!=NULL)
            x=x->left;
        return x;
        RedBlackNode *y=x->parent;
        while((y!=NULL) && (x==y->right))
        {
            x=y;
            y=y->parent;
        }
        return y;
    }
}
RedBlackNode* RedBlackTree::RB_Search(int val)
{
    RedBlackNode* x=root;
    while (x!=NULL)
    {
        if (val==x->key)
            return x;
        if (val<x->key)
            x=x->left;
        else x=x->right;
    }
    if (x==NULL)
        return NULL;
}
int main()
{
    RedBlackTree T;
    int inp;
    do
    {
    cout<<"The following operations may be performed on the binary search tree"<<endl;
    cout<<"Insertion - 1"<<endl;
    if (T.root!=NULL)
        cout<<"Deletion - 2"<<endl;
    cout<<"Search - 3"<<endl;
    cout<<"Exit - 4"<<endl;
    cout<<"Enter an option:";
    cin>>inp;
    switch(inp)
    {
        case 1:
        cout<<"Enter a value to insert";
        cin>>inp;
        T.Insert(inp);
        inp=1;
        break;
        case 2:
        cout<<"Enter the value of the node which needs deletion:";
        cin>>inp;
        T.RB_Delete(T.RB_Search(inp));
        inp=2;
        break;
        case 3:
        cout<<"Enter the value of the node that needs to be looked up:";
        cin>>inp;
        RedBlackNode *srch=T.RB_Search(inp);
        if (srch==NULL)
            cout<<"Not found";
        else
        {
            cout<<"Value:"<<inp<<" Color:"<<srch->color;
            cout<<"Parent:"<<srch->parent->key<<" Color:"<<srch->parent->color;
        }
        inp=3;
        break;
    }
    } while(inp!=4);
}