IN C PROGRAMMING LANGUAGE TASK MANAGER USING AVL TREE OR RED/BLACK TREE Task Man
ID: 3911056 • Letter: I
Question
IN C PROGRAMMING LANGUAGE TASK MANAGER USING AVL TREE OR RED/BLACK TREE
Task Manager For this problem you will try to emulate some basic functions of a Task Manager. You must support the addition and removal of tasks. Each task will be assigned a priority as a non-negative integer (1.000.000.000-highest. 0=lowest). No two distinctly named tasks will have the same priority. Additionally for a given run you can assume that each task with the same name will have the same priority Your Task Manager must support two types of operations. Type 1 is the creation of a new task. Type 2 is to determine the name of a task with a particular priority Input Specificatiorn The first line of input contains a single positive integer n (n s 10,000,000), which represents the total number of queries and addition deletions combined. Each of the following n lines begins with a single integer; the i-th line's integer describes the i-th operation type .When the beginning integer is 1 the operation is an add task operation. The remaining line will contain a task name followed by the task's priority Then the beginning integer is 2 the operation is the query operation. The remaining line will contain a single integer representing the desired task name's priority The name of each task will be composed strictly of at most 19 upper and lowercase Latin letters . . Output Specification For each attempted task addition you will output a single line containing either "ADDED" which means the task was not already present in the task list and was successfully added, or "REDUNDANT" which means that task was already in the list and therefore not added to the Task Manager For each name query operation you will output a single line containing either the associated name with the task or the string NON-EXISTANT", which means the task was not in the Task ManagerExplanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
char color;//color whether 'R' or 'B'
int key; //val of node
struct node *left;//ptr to left node
char id[20];
struct node *right;//ptr to right node
struct node *p;//parent pointer
}node;
node *root,*nul;//nul is sentinel node
int max_count=0,curr_count=0;
void create_sentinel(){ //A sentinel node is a black node to which all null pointers in tree point to.
node *p=(node *)malloc(sizeof(node));
if(p==NULL){
printf("Memory allocation failed ");
return ;
}
p->color='B';
p->left=NULL;
p->right=NULL;
nul=p;
root=nul;
root->p=nul;
}
/*Left rotation*/
void left_rotate(node *x){
node *y=x->right;
x->right=y->left;
if(y->left!=nul) y->left->p=x;
y->p=x->p;
if(x->p==nul) root=y;
else if(x==x->p->left) x->p->left=y;
else x->p->right=y;
y->left=x;
x->p=y;
}
/*Right rotation*/
void right_rotate(node *y){
node *x=y->left;
y->left=x->right;
if(x->right!=nul) x->right->p=y;
x->p=y->p;
if(y->p==nul) root=x;
else if(y==y->p->left) y->p->left=x;
else y->p->right=x;
x->right=y;
y->p=x;
}
/*corrects the color of the nodes by traversing up the tree*/
void insert_fixup(node *z){
node *y;
while(z->p->color=='R'){ //Upto parent color is red , as black color node can have its children of any color
if(z->p==z->p->p->left) { //If parent of z is left sibling
y=z->p->p->right;//y is right sibling of parent
if(y->color=='R'){//checks if color of y is R
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;
}
else if(z==z->p->right){//if z is right sibling
z=z->p;
left_rotate(z);
}
else { //if z is left sibling
z->p->color='B';
z->p->p->color='R';
right_rotate(z->p->p);
}
}
else{
y=z->p->p->left;
if(y->color=='R'){
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;
}
else if(z==z->p->left){
z=z->p;
right_rotate(z);
}
else {
z->p->color='B';
z->p->p->color='R';
left_rotate(z->p->p);
}
}
}
root->color='B';
}
/* Inserts independent of the color of nodes which will be fixed up in the insert-fixup-method*/
void insert(char *pid,int val){
node *n=(node *)malloc(sizeof(node));
if(n==NULL){
printf("Memory allocation failed ");
return ;
}
n->key=val;
strcpy(n->id,pid);
node *x,*y;
x=root;
y=nul;
while(x!=nul){
y=x;
if(n->key<x->key) x=x->left;
else x=x->right;
}
n->p=y;
if(y==nul) root=n;
else if(n->key<y->key) y->left=n;
else y->right=n;
n->left=nul;
n->right=nul;
n->color='R';
insert_fixup(n);
}
/* Searches for the noe*/
node *search(int val,node *curr){
if(curr==nul) return curr;
else if(curr->key==val) return curr;
else if(curr->key>val) return search(val,curr->left);
else return search(val,curr->right);
}
void sabfree(node *curr){
if(curr!=nul){
if(curr->left!=nul) sabfree(curr->left);
if(curr->right!=nul) sabfree(curr->right);
free(curr);
}
}
int main(){
int n;
scanf("%d",&n);
create_sentinel();
int count=0;
while(count<n){
int x;
scanf("%d",&x);
if(x==1){
char id[20];
int priority;
scanf("%s%d",id,&priority);
if(search(priority,root)!=nul) printf("REDUNDANT ");
else {
insert(id,priority);
printf("ADDED ");
}
}
else if(x==2){
int y;
scanf("%d",&y);
node *z=search(y,root);
if(z==nul) printf("NON-EXISTANT ");
else printf("%s ",z->id);
}
count++;
}
sabfree(root);
free(nul);
}