Question

Create a communication information system for a company with using Red-Black Tree Method. In this system the users are allowed to search an employee from employee's registration number(id) and retreive the department number(id) and that employee's internal phone number. Also, if the employee they are looking for is not in the tree, they can add it. (in accordance with the red-black tree properties)

a) Implement the Employee class:

- Registration number (an integer)

- Department ID (an integer)

- Internal Phone Number (an integer) - all other required procedures.

b) Implement a Red-Black Tree. You will store your employee objects in a Red-Black Tree. In your Red-Black Tree implementation you can directly use the header file that we shared with you on the moodle (RedBlackTree.h) or you can write yourself. This tree will have:

- insert function: to insert an employee object into the Red-Black Tree. (in accordance with the red- black tree properties)

- search function: to find a employee in the tree

c) Implement a main function. In the main function:

- Instantiate your Red-Black Tree object.

- Instantiate and insert the following employee objects into the tree:

- Registration number : 1001, Department id : 51, Phone number: 6467 - Registration number : 1002, Department id : 43, Phone number: 2359 - Registration number : 1010, Department id : 34, Phone number: 4342 - Registration number : 1008, Department id : 21, Phone number: 6761 - Registration number : 2001, Department id : 45, Phone number: 2345 - Registration number : 2006, Department id : 23, Phone number: 6862

SAMPLE RUN (after Red-Black Tree is created and filled with employee objects): Enter Employee’s Registration Number : 1001

Department id is : 51. Internal phone number is : 6467

Continue (y/n): y

Enter Employee’s Registration Number : 2008

Employee not found !

Do you want to add this employee to the system ? : y

What is the Department id and Internal phone number? : 63 8469

Added succesfully.

Continue (y/n): y

Enter Employee’s Registration Number : 2008

Department id is : 63. Internal phone number is : 8469

Continue (y/n): n

Bye (Note : Those written in bold are entered by the user.

Write with using JAVA

Answer 1

ANSWER :

C++ code :

#include<iostream>
using namespace std;
class Employee{
public:
Employee *left,*right,*par; //left-child,right-child,parent-node
int reg,dept,phone; //variables to store the detials of the employee
char color; //to give color to the node

Employee(int x,int y,int z,Employee*l=0,Employee*r=0,Employee*pa=0,char col='r')
{
reg=x;
dept=y;
phone=z;
left=l;
right=r;
par=pa;
color=col;
}
};
class RBT{

public:
Employee *root;
Employee *nil;

RBT() //constructor
{
nil=new Employee(0,0,0);
nil->color='b';
root=nil;
}

void Insert(int x,int y,int z) //Inserting the elements in the tree
{
Employee *p,*prev=nil,*q;

if(root==nil)
{
p=new Employee(x,y,z,nil,nil,nil,'b');
root=p;
}
else{
p=new Employee(x,y,z,nil,nil,nil,'r');
q=root;
while(q!=nil)
{ prev=q;
if(x<q->reg)
q=q->left;
else
q=q->right;
}
p->par=prev;
if(x<prev->reg)
{
prev->left=p;
// p->par=prev;
}
else{
prev->right=p;
//p->par=prev;
}
}
Insert_fixup(p);
}

void Insert_fixup(Employee *t) //fixing up the tree after insertion of new elements by rotating the tree
{
Employee *u;
if(root==t)
{
t->color='b';
return;
}
while(t->par!=nil&&t->par->color=='r')
{
Employee *g=t->par->par;
if(g->left==t->par)
{
if(g->right!=nil)
{
u=g->right;
if(u->color=='r')
{
t->par->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->par->right==t)
{
t=t->par;
left_rotate(t);
}
t->par->color='b';
g->color='r';
right_rotate(g);
}
}
else
{
if(g->left!=nil)
{
u=g->left;
if(u->color=='r')
{
t->par->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->par->left==t)
{
t=t->par;
right_rotate(t);
}
t->par->color='b';
g->color='r';
left_rotate(g);
}
}
root->color='b';
}
}
void left_rotate(Employee *x) //to adjust tree due to new entries by ritating left
{
Employee *y;
y= x->right;
x->right=y->left;
if(y->left!=nil)
y->left->par=x;
y->par= x->par;
if(x->par==nil)
root =y;
else if (x==x->par->left)
x->par->left=y;
else
x->par->right = y;
y->left=x;
x->par=y;
}
void right_rotate(Employee *x) //to adjust tree due to new entries by rotating right
{
Employee *y;
y= x->left;
x->left=y->right;
if(y->right!=nil)
y->right->par=x;
y->par= x->par;
if(x->par==nil)
root =y;
else if (x==x->par->right)
x->par->right=y;
else
x->par->left = y;
y->right=x;
x->par=y;
}
Employee* search(int x) //to serach for an employee
{
int f=0;
Employee*p=root;
while(p!=0)
{
if(x==p->reg)
{
f=1;
break;
}
else if(x<p->reg)
{
p=p->left;
}
else
{
p=p->right;
}
}
if(f==1)
return p;
}
void display(Employee *t) //to display employee
{
if(t!=nil)
{
cout<<"\nDepartment Id of Employee is: "<<t->dept;
cout<<"\nInternal Phone number of Employee: "<<t->phone;
}
}
void menu()
{
char ch;
Insert(1001,51,6467); //filling the tree with details
Insert(1002,43,2359);
Insert(1010,34,4342);
Insert(1008,21,6761);
Insert(2001,45,2345);
Insert(2006,23,6862);
do
{
int q;
cout<<"Enter Employee's Registration Number: ";
cin>>q;
if(search(q)) //search for an employee
{
cout<<"Employee Found!";
display(search(q));
}
else
{
char a;
cout<<"Employee not Found!";
cout<<"\nDo you want to add this employee to the system? ";
cin>>a;
if(a=='y')
{
int d,p;
cout<<"What is the Deprtment Id and Internal Phone number?: ";
cin>>d; //enter department
cin>>p; //enter phone
Insert(q,d,p); //insert this in the tree
cout<<"Added Successfully.";
}
}
cout<<"\nContinue?(y/n): ";
cin>>ch;
}while(ch=='y'||ch=='Y');
cout<<"bye";
}
};
int main()
{
RBT rbt;
rbt.menu();
return(0);
}

Output :