Help! Help! Help! C-Programming code for maintaining a red black tree where 0-Ex

Question

Help! Help! Help! C-Programming code for maintaining a red black tree where 0-Exit the program

1 x- Insert positive integer key x, unless x is already present in the tree. (Error message if x is a duplicate.) Besides inserting the key, odd subtree root ranks must be updated. The odd subtree root rank of a node is the number of odd keys in the subtree to the left.

2 x- Find the odd rank of x,i.e. the number of odd keys in the tree that are smaller than x (error message if x is not in the tree).The numbers to the left of each node in the diagram below are the odd ranks.

3k- Find the smallest and largest keys with odd rank k (error message if there is no key with odd rank k)

4- Perform an audit on the odd subtree root rank at each node to give a final indication that the tree is “clean” or “corrupt”.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
enum nodeColor {
RED,
BLACK
};

struct rbNode {
int data, color;
struct rbNode *link[2];
};

struct rbNode *root = NULL;

struct rbNode * createNode(int data) {
struct rbNode *newnode;
newnode = (struct rbNode *)malloc(sizeof(struct rbNode));
newnode->data = data;
newnode->color = RED;
newnode->link[0] = newnode->link[1] = NULL;
return newnode;
}

void insertion (int data) {
struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr;
int dir[98], ht = 0, index;
ptr = root;
if (!root) {
root = createNode(data);
return;
}
stack[ht] = root;
dir[ht++] = 0;
/* find the place to insert the new node */
while (ptr != NULL) {
if (ptr->data == data) {
printf("Duplicates Not Allowed!! ");
return;
}
index = (data - ptr->data) > 0 ? 1 : 0;
stack[ht] = ptr;
ptr = ptr->link[index];
dir[ht++] = index;
}
/* insert the new node */
stack[ht - 1]->link[index] = newnode = createNode(data);
while ((ht >= 3) && (stack[ht - 1]->color == RED)) {
if (dir[ht - 2] == 0) {
yPtr = stack[ht - 2]->link[1];
if (yPtr != NULL && yPtr->color == RED) {
stack[ht - 2]->color = RED;
stack[ht - 1]->color = yPtr->color = BLACK;
ht = ht -2;
} else {
if (dir[ht - 1] == 0) {
yPtr = stack[ht - 1];
} else {
xPtr = stack[ht - 1];
yPtr = xPtr->link[1];
xPtr->link[1] = yPtr->link[0];
yPtr->link[0] = xPtr;
stack[ht - 2]->link[0] = yPtr;
}
xPtr = stack[ht - 2];
xPtr->color = RED;
yPtr->color = BLACK;
xPtr->link[0] = yPtr->link[1];
yPtr->link[1] = xPtr;
if (xPtr == root) {
root = yPtr;
} else {
stack[ht - 3]->link[dir[ht - 3]] = yPtr;
}
break;
}
} else {
yPtr = stack[ht - 2]->link[0];
if ((yPtr != NULL) && (yPtr->color == RED)) {
stack[ht - 2]->color = RED;
stack[ht - 1]->color = yPtr->color = BLACK;
ht = ht - 2;
} else {
if (dir[ht - 1] == 1) {
yPtr = stack[ht - 1];
} else {
xPtr = stack[ht - 1];
yPtr = xPtr->link[0];
xPtr->link[0] = yPtr->link[1];
yPtr->link[1] = xPtr;
stack[ht - 2]->link[1] = yPtr;
}
xPtr = stack[ht - 2];
yPtr->color = BLACK;
xPtr->color = RED;
xPtr->link[1] = yPtr->link[0];
yPtr->link[0] = xPtr;
if (xPtr == root) {
root = yPtr;
} else {
stack[ht - 3]->link[dir[ht - 3]] = yPtr;
}
break;
}
}
}
root->color = BLACK;
}

void oddrank(int data) {
struct rbNode *temp = root;
int diff;

while (temp != NULL) {
diff = data - temp->data;
if (diff > 0) {
temp = temp->link[1];
} else if (diff < 0) {
temp = temp->link[0];
} else {
printf("Search Element Found!! ");
return;
}
}
printf("Given Data Not Found in RB Tree!! ");
return;
}

void smalllargekeys(struct rbNode *node) {
if (node) {
inorderTraversal(node->link[0]);
printf("%d ", node->data);
inorderTraversal(node->link[1]);
}
return;
}

  
int main() {
int ch, data;
while (1) {
printf("0. Exit ");
printf("1. Insertion ");
printf("2. Find the odd rank ");
printf("3. Find the smallest and largest keys ");
  
printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) {
  
case 0:
exit(0);
case 1:
printf("Enter the data to insert:");
scanf("%d", &data);
insertion(data);
break;
case 2:
printf("Enter the element to find odd Rank:");
scanf("%d", &data);
oddrank(data);
break;
case 3:
printf("Enter a odd rank to find Smallest and largest keys:");
scanf("%d", &data);
smalllargekeys(data);
break;
case 4:
audit(root);
printf(" ");
break;
default:
printf("You have entered wrong option!! ");
break;
}
printf(" ");
}
return 0;
}
  

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.