#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<
