Create a communication information system for a company with using Red-Black Tree Method
• Write this program with using C/C++, C#, Java or Python. Explain your code with comments.
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.)
HEADER FILE:
using namespace std;
template <class T>
class RBNode
{
private:
bool isRed;
T value;
RBNode<T> *left, *right, *parent;
public:
RBNode(T value)
{
this->isRed = true;
this->value = value;
left = NULL;
right = NULL;
parent = NULL;
}
void Recolor()
{
if (this->isRed) this->isRed = false;
else this->isRed = true;
}
bool IsRed()
{
return isRed;
}
T GetValue()
{
return this->value;
}
RBNode* GetLeft()
{
return this->left;
}
RBNode* GetRight()
{
return this->right;
}
RBNode* GetParent()
{
return this->parent;
}
void ClearParent()
{
this->parent = NULL;
}
void SetLeft(RBNode* left)
{
this->left = left;
if(left != NULL) left->parent = this;
}
void SetRight(RBNode* right)
{
this->right = right;
if(right != NULL) right->parent = this;
}
};
template <class T> class RedBlackTree
{
private:
RBNode<T>* root;
RBNode<T>* AccessNode(RBNode<T> *root, T value)
{
if(root->GetValue() == value)
{
return root;
}
else if(root->GetValue() > value)
{
if(root->GetLeft() == NULL)
{
return NULL;
}
else
{
return this->AccessNode(root->GetLeft(), value);
}
}
else
{
if(root->GetRight() == NULL)
{
return NULL;
}
else
{
return this->AccessNode(root->GetRight(), value);
}
}
}
void InsertNode(RBNode<T> *root, T value)
{
RBNode<T>* insertedNode = NULL;
if(root->GetValue() == value)
{
//skip
}
else if(root->GetValue() > value)
{
if(root->GetLeft() == NULL)
{
insertedNode = new RBNode<T>(value);
root->SetLeft(insertedNode);
}
else
{
this->InsertNode(root->GetLeft(), value);
}
}
else
{
if(root->GetRight() == NULL)
{
insertedNode = new RBNode<T>(value);
root->SetRight(insertedNode);
}
else
{
this->InsertNode(root->GetRight(), value);
}
}
if (insertedNode == NULL) return;
this->SolveDoubleRedProblem(root);
insertedNode = NULL;
}
void SolveDoubleRedProblem(RBNode<T> *root)
{
if (root->IsRed() == false) return;
if (root == root->GetParent()->GetLeft())
{
if (root->GetParent()->GetRight() == NULL || !root->GetParent()->GetRight()->IsRed()) this->RightRotate(root);
else
{
root->Recolor();
root->GetParent()->GetRight()->Recolor();
root->GetParent()->Recolor();
if (root->GetParent()->GetParent() == NULL)
{
root->GetParent()->Recolor();
return;
}
SolveDoubleRedProblem(root->GetParent()->GetParent());
}
}
else
{
if (root->GetParent()->GetLeft() == NULL || !root->GetParent()->GetLeft()->IsRed()) this->LeftRotate(root);
else
{
root->Recolor();
root->GetParent()->GetLeft()->Recolor();
root->GetParent()->Recolor();
if (root->GetParent()->GetParent() == NULL)
{
root->GetParent()->Recolor();
return;
}
SolveDoubleRedProblem(root->GetParent()->GetParent());
}
}
}
void LeftRotate(RBNode<T> *root)
{
RBNode<T> *parent = root->GetParent();
if (root->GetLeft() != NULL && root->GetLeft()->IsRed())
{
RBNode<T> *badChild = root->GetLeft();
root->SetLeft(badChild->GetRight());
badChild->SetRight(root);
parent->SetRight(badChild);
root = badChild;
}
root->Recolor();
parent->Recolor();
parent->SetRight(root->GetLeft());
if (parent->GetParent() != NULL)
{
if (parent->GetParent()->GetLeft() == parent) parent->GetParent()->SetLeft(root);
else parent->GetParent()->SetRight(root);
}
else
{
this->root = root;
this->root->ClearParent();
root = this->root;
}
root->SetLeft(parent);
}
void RightRotate(RBNode<T> *root)
{
RBNode<T> *parent = root->GetParent();
if (root->GetRight() != NULL && root->GetRight()->IsRed())
{
RBNode<T> *badChild = root->GetRight();
root->SetRight(badChild->GetLeft());
badChild->SetLeft(root);
parent->SetLeft(badChild);
root = badChild;
}
root->Recolor();
parent->Recolor();
parent->SetLeft(root->GetRight());
if (parent->GetParent() != NULL)
{
if (parent->GetParent()->GetLeft() == parent) parent->GetParent()->SetLeft(root);
else parent->GetParent()->SetRight(root);
}
else
{
this->root = root;
this->root->ClearParent();
root = this->root;
}
root->SetRight(parent);
}
public:
RedBlackTree()
{
this->root = NULL;
}
bool IsEmpty()
{
return root == NULL;
}
RBNode<T>* AccessNode(T value)
{
if (this->IsEmpty()) return NULL;
else return this->AccessNode(root, value);
}
void InsertNode(T value)
{
if (this->IsEmpty())
{
this->root = new RBNode<T>(value);
this->root->Recolor();
}
else this->InsertNode(this->root, value);
}
};
Homework Answers
#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 Department 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;
cout<<"\n";
}while(ch=='y'||ch=='Y');
}
};
int main()
{
RBT rbt;
rbt.menu();
return(0);
}
Add Answer to:
Create a communication information system for a company with using Red-Black Tree Method
Create a communication information system for a company with using Red-Black Tree Method.
PLEASE USE THE HEADER FILE THAT I ADDED TO THE END OF THE QUESTIONWrite this program with using C/C++, C#, Java or Python. Explain your code with comments. Create a communication information system for a company with using Red-Black Tree Method. Inthis 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 theemployee they are looking for is not in the tree, they can add it....
Removing Nodes from a Binary Tree in Java This section requires you to complete the following...
Removing Nodes from a Binary Tree in Java This section requires you to complete the following method within BinaryTree.java: public void remove(K key) { } The remove method should remove the key from the binary tree and modify the tree accordingly to maintain the Binary Search Tree Principle. If the key does not exist in the binary tree, no nodes should be removed. In case there is a non-null left child, it should take the place of the removed node....
Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation...
Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation in Java #########LinkedBinary Tree class######### public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> { //---------------- nested Node class ---------------- /** Nested static class for a binary tree node. */ protected static class Node<E> implements Position<E> { private E element; // an element stored at this node private Node<E> parent; // a reference to the parent node (if any) private Node<E> left; // a reference to the left...
public class Buildbst { private int data; private Buildbst left; private Buildbst right; //Set the binary...
public class Buildbst { private int data; private Buildbst left; private Buildbst right; //Set the binary search tree public Buildbst(int data) { this.data = data; this.left = null; this.right =null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Buildbst getLeft() { return left; } public void setLeft(Buildbst left) { this.left = left; } public Buildbst getRight() { return right; } public void setRight(Buildbst right) { this.right = right; } }...
Please create a class in Java that completes the following conditions MorseTree.java /* This program will...
Please create a class in Java that completes the
following conditions
MorseTree.java
/* This program will read in letters followed by their morse
code
* and insert them properly in a tree based on the amount of
symbols
* it has and whether they are left or right descendent.
Finally
* it prints a few certain nodes.
*/
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class MorseTree {
public static void main(String[] args) throws
FileNotFoundException {
//...
Test Data would be as follows: Using java language. Build an expression tree. • When you...
Test Data would be as follows:
Using java language. Build an expression tree. • When you see a number: o you create a new node with the number as the data. o Then you push the new node to the stack. . When you see a binary operator: 0 You create a new Node for the operator. Then you pop and set the right child. Then you pop and set the left child o Then you push the new node...
Using the following implementation of Tree class Node { public int iData; // data item (key) public...
Using the following implementation of Tree class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); } } // end class Node //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
PLEASE HELP! The assignment details are in the *noted part of the code. I REALLY need...
PLEASE HELP! The assignment details are in the *noted part of the code. I REALLY need help. import java.util.LinkedList; public class TwoDTree { private TwoDTreeNode root; private int size; public TwoDTree() { clear(); } /** * Returns true if a point is already in the tree. * Returns false otherwise. * * The traversal remains the same. Start at the root, if the tree * is not empty, and compare the x-coordinates of the point passed * in and...
Since we do not want to have to rewrite this code when the element type changes,...
Since we do not want to have to rewrite this code when the element type changes, this classes uses a Comparator to assist in ordering the elements. You will need to complete the siftUpComparator() and siftDownComparator() methods in the LinkedHeap Class. siftUp §Added element may violate heap-order property §siftUp() restores order starting at added node §Processing will continue working up the tree until: úFinds properly ordered node & parent úReaches the root (reaches node without parent) siftDown §Restores heap’s order...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Please create a class in Java that completes the
following conditions
MorseTree.java
/* This program will read in letters followed by their morse
code
* and insert them properly in a tree based on the amount of
symbols
* it has and whether they are left or right descendent.
Finally
* it prints a few certain nodes.
*/
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class MorseTree {
public static void main(String[] args) throws
FileNotFoundException {
//...
Test Data would be as follows:
Using java language. Build an expression tree. • When you see a number: o you create a new node with the number as the data. o Then you push the new node to the stack. . When you see a binary operator: 0 You create a new Node for the operator. Then you pop and set the right child. Then you pop and set the left child o Then you push the new node...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Most questions answered within 3 hours.
-
New Air Heating and Cooling, manufactures furnaces and central
air units. The company pride itself on...
asked 8 minutes ago -
A coach uses a new technique to train gymnasts. Seven
gymnasts were randomly selected and their...
asked 2 hours ago -
While rotating the tires on your car you notice a rock [mass =
0.1 Kg] stuck...
asked 4 hours ago -
Using MARS simulator, write MIPS programs according to
the following scenarios: Receive a positive integer number...
asked 5 hours ago -
An object in front of a concave mirror has a real image that is
11.5 cm...
asked 6 hours ago -
Consider the reaction, C3 H8 + O2 --> CO2 + H2O. How many
moles of O2...
asked 7 hours ago -
You and your opponent both roll a fair die. If you both roll the
same number,...
asked 8 hours ago -
In a study of the accuracy of fast food drive-through orders,
Restaurant A had 257 accurate...
asked 8 hours ago -
Identify and describe in detail the four categories of
institutions that could be included in a...
asked 8 hours ago -
In python
class Customer:
def __init__(self, customer_id, last_name, first_name, phone_number, address):
self._customer_id = int(customer_id)
self._last_name =...
asked 8 hours ago -
What is an example of a limitation in implementing a new
ERP system and how it...
asked 8 hours ago -
In a section of 9.7cm of an artery with a radius of 2.6mm there
is a...
asked 8 hours ago