#includeusing else { if(ptr==ptr->parent->left) ptr->parent->left=rotate; else ptr->parent->right=rotate; } rotate->left=ptr;

#includeusing namespace std;struct Node{       int data;       Node *parent;       char color;       Node *left;       Node *right;};class RBT{      Node *root;      Node *q;   public :   void init()   {   q=NULL;   root=NULL;   } void insert_tree()   { int value,i=0; cout<<"Enter Element of the Node to be inserted: "; cin>>value; Node *ptr,*q; Node *temp=new Node; temp->data=value; temp->left=NULL; temp->right=NULL; temp->color=’r’; ptr=root; q=NULL; if(root==NULL) {    root=temp;    temp->parent=NULL; } else { while(ptr!=NULL) {   q=ptr;   if(ptr->datadata)   {   ptr=ptr->right;   }   else   {   ptr=ptr->left;   } } temp->parent=q; if(q->datadata) {   q->right=temp; } else {   q->left=temp; }   } fix_insertion(temp); }      void fix_insertion(Node * temp) { Node *obj; if(root==temp) { temp->color=’b’; return; } while((temp->parent!=NULL)&&(temp->parent->color==’r’)) {    Node *fix=temp->parent->parent;    if(fix->left==temp->parent)    { if(fix->right!=NULL) {   obj=fix->right;   if(obj->color==’r’)   {    temp->parent->color=’b’;    obj->color=’b’;    fix->color=’r’;    temp=fix;   } } else { if(temp->parent->right==temp) { temp=temp->parent; rotateleft(temp); } temp->parent->color=’b’; fix->color=’r’; rotateright(fix); }    }    else    { if(fix->left!=NULL) { obj=fix->left; if(obj->color==’r’) {   temp->parent->color=’b’;   obj->color=’b’;   fix->color=’r’;   temp=fix; } } else { if(temp->parent->left==temp) {    temp=temp->parent;    rotateright(temp); } temp->parent->color=’b’; fix->color=’r’; rotateleft(fix); }    }    root->color=’b’; } }      void rotateleft(Node * ptr) { if(ptr->right==NULL) {    return; } else {    Node *rotate=ptr->right;    if(rotate->left!=NULL)    {   ptr->right=rotate->left;   rotate->left->parent=ptr;    }    else   ptr->right=NULL;    if(ptr->parent!=NULL) rotate->parent=ptr->parent;    if(ptr->parent==NULL) root=rotate;    else    {    if(ptr==ptr->parent->left)    ptr->parent->left=rotate;    else    ptr->parent->right=rotate;    }    rotate->left=ptr;    ptr->parent=rotate; } }      void rotateright(Node * ptr)   { if(ptr->left==NULL)   return ; else { Node *rotate=ptr->left; if(rotate->right!=NULL) {   ptr->left=rotate->right;   rotate->right->parent=ptr; } else { ptr->left=NULL; } if(ptr->parent!=NULL) { rotate->parent=ptr->parent; } if(ptr->parent==NULL) {    root=rotate; } else { if(ptr==ptr->parent->left) {    ptr->parent->left=rotate; } else {    ptr->parent->right=rotate; } } rotate->right=ptr; ptr->parent=rotate; }   }      void deletenode()    { if(root==NULL) {    cout<<" Empty Tree." ;    return ; } int value; cout<<" Enter the data of the Node to be deleted: "; cin>>value; Node *delptr; delptr=root; Node *temp1=NULL; Node *temp2=NULL; int found=0; while(delptr!=NULL&&found==0) {    if(delptr->data==value)    {    found=1;    }    if(found==0)    { if(delptr->dataright; } else { delptr=delptr->left; }    } } if(found==0) { cout<<" Element Not Found."; return; } else { cout<<" Deleted Element: "<data; cout<<" Colour: "; if(delptr->color==’b’) { cout<<"Black "; } else { cout<<"Red "; } if(delptr->parent!=NULL) {    cout<<" Parent: "<parent->data; } else {  cout<<" There is no parent of the Node.  "; } if(delptr->right!=NULL) {    cout<<" Right Child: "<right->data; } else {    cout<<" There is no right child of the Node.  "; } if(delptr->left!=NULL) {    cout<<" Left Child: "<left->data; } else {    cout<<" There is no left child of the Node.  "; } cout<<" Node Deleted."; if(delptr->left==NULL||delptr->right==NULL) {   temp1=delptr; } else {   temp1=next(delptr); } if(temp1->left!=NULL) {   temp2=temp1->left; } else {   if(temp1->right!=NULL)   {    temp2=temp1->right;   }   else   {   temp2=NULL;   } } if(temp2!=NULL) {   temp2->parent=temp1->parent; } if(temp1->parent==NULL) {   root=temp2; } else { if(temp1==temp1->parent->left) { temp1->parent->left=temp2; } else { temp1->parent->right=temp2; } } if(temp1!=delptr) { delptr->color=temp1->color; delptr->data=temp1->data; } if(temp1->color==’b’) { fix_deletion(temp2); } } }      Node* next(Node * ptr)   {   Node *temp=NULL; if(ptr->left!=NULL) { temp=ptr->left; while(temp->right!=NULL)   temp=temp->right; } else { temp=ptr->right; while(temp->left!=NULL)   temp=temp->left; } return temp;   }      void fix_deletion(Node * ptr) { Node *temp; while(ptr!=root&&ptr->color==’b’) {   if(ptr->parent->left==ptr)   {   temp=ptr->parent->right;   if(temp->color==’r’)   { temp->color=’b’; ptr->parent->color=’r’; rotateleft(ptr->parent); temp=ptr->parent->right;   }   if(temp->right->color==’b’&&temp->left->color==’b’)   { temp->color=’r’; ptr=ptr->parent;   }   else   {   if(temp->right->color==’b’)   { temp->left->color==’b’; temp->color=’r’; rotateright(temp); temp=ptr->parent->right;   }   temp->color=ptr->parent->color;   ptr->parent->color=’b’;   temp->right->color=’b’;   rotateleft(ptr->parent);   ptr=root;   }   }   else   {   temp=ptr->parent->left;   if(temp->color==’r’)   { temp->color=’b’; ptr->parent->color=’r’; rotateright(ptr->parent); temp=ptr->parent->left;   }   if(temp->left->color==’b’&&temp->right->color==’b’)   { temp->color=’r’; ptr=ptr->parent;   }   else   { if(temp->left->color==’b’) {   temp->right->color=’b’;   temp->color=’r’;   rotateleft(temp);   temp=ptr->parent->left; } temp->color=ptr->parent->color; ptr->parent->color=’b’; temp->left->color=’b’; rotateright(ptr->parent); ptr=root;   }   }    ptr->color=’b’;    root->color=’b’; } }      void disp()   { display(root);   }      void display( Node *ptr)   { if(root==NULL) {   cout<<" Empty Tree.";   return ; } if(ptr!=NULL) { cout<<" Node: "; cout<<" data: "<data; cout<<" Colour: "; if(ptr->color==’b’) { cout<<"Black"; } else { cout<<"Red"; } if(ptr->parent!=NULL) {    cout<<" Parent: "<parent->data; } else {    cout<<" There is no parent of the Node.  "; } if(ptr->right!=NULL) {    cout<<" Right Child: "<right->data; } else {    cout<<" There is no right child of the Node.  "; } if(ptr->left!=NULL) {    cout<<" Left Child: "<left->data; } else {    cout<<" There is no left child of the Node.  "; } cout<left) { cout<<" Left: "; display(ptr->left); } if(ptr->right) { cout<<" Right: "; display(ptr->right); } }   }      void search()   { if(root==NULL) {    cout<<" Empty Tree " ;    return  ; } int value; cout<<" Enter data of the Node to be searched: "; cin>>value; Node *temp=root; int found=0; while(temp!=NULL&& found==0) { if(temp->data==value) { found=1; } if(found==0) { if(temp->dataright; } else {   temp=temp->left; } } } if(found==0) {   cout<<" Element Not Found."; } else { cout<<" FOUND Node: "; cout<<" data: "<data; cout<<" Colour: "; if(temp->color==’b’) { cout<<"Black"; } else { cout<<"Red"; } if(temp->parent!=NULL) {    cout<<" Parent: "<parent->data; } else { cout<<" There is no parent of the Node.  "; } if(temp->right!=NULL) {    cout<<" Right Child: "<right->data; } else {    cout<<" There is no right child of the Node.  "; } if(temp->left!=NULL) {    cout<<" Left Child: "<left->data; } else {    cout<<" There is no left child of the Node.  "; } cout<>choice;                if(choice==1) { tree.insert_tree(); cout<<" Node Inserted. "; } else if(choice==2) { tree.deletenode(); } else if(choice==3) { tree.search(); } else if(choice==4) { tree.disp(); } else if(choice==5) { exit=1; }                cout<