Я создал RBT с двумя типами ввода, одним типом операции (N, S, P, U, C, -), и после этого серией чисел в соответствии с вводом,
Проблема, с которой я сталкиваюсь, заключается в том, что при выполнении тестовых случаев моя вставка исправления не работает должным образом, я пропустил некоторые случаи или у меня есть некоторые логические ошибки
#include <stdio.h>
#include <stdlib.h>
struct RBT
{ // binary search tree where the numerical items will be stored.
int data,height;
char color;
struct RBT *left, *right, *parent;
};
struct RBT *RBTnode ( int key )
{ // function to create new node in binary search tree
struct RBT *temp = (struct RBT *) malloc(sizeof(struct RBT));
temp->data = key;
temp->left=NULL;
temp->right=NULL;
temp-> parent = NULL;
temp -> height = 1;
temp -> color = 'R';
return temp;
}
//int blackheight = 1 ;
struct RBT* insertRBTitem ( struct RBT* node, int item, struct RBT* par )
{ // function to insert value in newly created node in binary search tree
if (node == NULL)
{
node = RBTnode(item);
node -> parent = par;
node->color = 'R';
// if( blackheight % 2 == 0)
// {
// node -> color = 'R';
// blackheight ++;
// }
// else if( blackheight % 2 == 1)
// {
// node -> color = 'B';
// blackheight ++;
// }
}
else if (item < node -> data)
{
node->left = insertRBTitem(node->left, item, node);
}
else
{
node->right = insertRBTitem(node->right, item, node);
}
return node;
}
void left_rotate (struct RBT* root, int key)
{
//for left rotating a given node in RBT
struct RBT *item = (struct RBT *) malloc(sizeof(struct RBT));
while(root -> data != key)
{
if(root->data > key)
{
root = root->left;
}
else if(root-> data < key)
{
root = root->right;
}
}
if (root -> data == key)
{
item = root;
}
if(item -> right != NULL)
{
struct RBT* par = item -> parent;
struct RBT* itemr = item -> right;
struct RBT* temp = itemr -> left;
par -> right = itemr;
itemr -> parent = par;
itemr -> left = item;
item -> parent = itemr;
item -> right = temp;
}
}
void right_rotate ( struct RBT* root , int key )
{
//for right rotating a given node in RBT
struct RBT *item = (struct RBT *) malloc(sizeof(struct RBT));
while(root -> data != key)
{
if(root->data > key)
{
root = root->left;
}
else if(root-> data < key)
{
root = root->right;
}
}
if (root -> data == key)
{
item = root;
}
if( item -> left != NULL)
{
struct RBT* par = item -> parent;
struct RBT* iteml = item -> left;
struct RBT* temp = iteml -> right;
par -> left = iteml;
iteml -> parent = par;
iteml -> right = item;
item -> parent = iteml;
item -> left = temp;
}
}
int searchRBT(struct RBT *item, int key)
{// retrun binary value, 1 if no. is present in RBT, 0 if not
if(item == NULL )
return 0;
else
{
if(item->data > key)
return searchRBT(item->left,key);
else if(item->data < key)
return searchRBT(item->right,key);
else
return 1;
}
}
void deleteTree(struct RBT* item){
// for freeing the memory of RBT
if(item == NULL )
return;
else
{
if(item->left != NULL)
return deleteTree(item->left);
if(item->right != NULL)
return deleteTree(item->right);
free(item);
}
}
int printPreOrder(struct RBT *item)
{ // doing pre-order traversal, and printing visited node's value
if(item == NULL)
{
return 0;
}
printf(" %d %c ",item->data,item->color);
printPreOrder(item->left);
printPreOrder(item->right);
}
void childprinter(struct RBT *item, int key)
{
//prints the child nodes of given node,
int parentnode,grandparentnode;
struct RBT* templ = NULL;
struct RBT* tempr = NULL;
if( searchRBT(item,key) == 1 )
{
while(item -> data != key)
{
if(item->data > key)
{ item = item->left;
//printf("0");
//printpath(item,key);
}
else if(item->data < key)
{ item = item->right;
//printf("1");
//printpath(item,key);
}
}
//printf("%d\n",item->data);
if (item -> data == key)
{
//printf("%d",grp->data);
if(item -> left ==NULL)
{
printf("L B");
}
else
{
templ = item->left;
printf("%d %c ",templ->data,templ->color);
}
if(item -> right == NULL)
{
printf(" L B");
}
else
{
tempr = item->right;
printf(" %d %c",tempr->data,tempr->color);
}
}
}
else
{
printf("-1");
}
}
struct RBT* succesor ( struct RBT * item , int key)
{
//finds the node's succesor.
struct RBT *temp = (struct RBT *) malloc(sizeof(struct RBT));
struct RBT *temp1 = (struct RBT *) malloc(sizeof(struct RBT));
while(item -> data != key)
{
if(item->data > key)
{
item = item->left;
}
else if(item->data < key)
{
item = item->right;
}
}
if (item -> data == key)
{
temp = item;
}
if( temp -> right != NULL)
{
temp = temp -> right;
while (temp -> left != NULL)
{
temp = temp -> left;
}
return temp;
//printf(" %d %c /n",item->data,item->color);
}
else if(temp -> right == NULL)
{
temp1 = temp -> parent;
while( temp1 -> left != temp )
{
temp1 = temp1 -> parent;
temp = temp -> parent;
}
return temp1;
}
}
void uncleprinter(struct RBT *item, int key)
{
//print the uncle of the given nodes data.
int parentnode,grandparentnode;
if( searchRBT(item,key) == 1 )
{
while(item -> data != key)
{
if(item->data > key)
{ item = item->left;
//printf("0");
//printpath(item,key);
}
else if(item->data < key)
{ item = item->right;
//printf("1");
//printpath(item,key);
}
}
//printf("%d\n",item->data);
if (item -> data == key)
{
struct RBT* par = item -> parent;
struct RBT* grp = par -> parent;
//printf("%d",grp->data);
if(par ==NULL)
{
printf("-1\n");
return;
}
else if(grp==NULL)
{
printf("-1\n");
return;
}
else
{
if( par == grp->left )
{
printf(" %d %c",grp->right->data,grp->right->color);
}
if( par== grp->right)
{
printf(" %d %c",grp->left->data,grp->right->color);
}
}
}
}
else
{
printf("-1");
}
}
void printpath(struct RBT *item, int key)
{
// prints the path of node of given number, from root ( top ) node
// print 1 for going in right subtree, 0 for going in left sub tree.
if( searchRBT(item,key) == 1 )
{
if (item -> data == key)
{
printf(" %c \n",item->color);
}
else if(item->data > key)
{ item = item->left;
printf("0");
printpath(item,key);
}
else if(item->data < key)
{ item = item->right;
printf("1");
printpath(item,key);
}
}
else
{
printf("-1");
}
}
void fixinsert ( struct RBT* root , int key)
{// fixing the RBT after inserting a node.
// struct RBT *item = (struct RBT *) malloc(sizeof(struct RBT));
struct RBT *temp = root;
while(temp -> data != key)
{
if(temp -> data > key)
{
temp = temp->left;
}
else if(temp -> data < key)
{
temp = temp -> right;
}
}
struct RBT *uncle;
if(root==temp)
{
temp->color='B';
return ;
}
while(temp -> parent != NULL && temp -> parent -> color == 'R')
{
struct RBT *grand=temp -> parent -> parent;
if(grand -> left == temp -> parent)
{
if(grand -> right != NULL)
{
uncle = grand -> right;
if(uncle -> color=='R')
{
temp -> parent -> color = 'B';
uncle -> color = 'B';
grand -> color = 'R';
temp = grand;
}
}
else
{
if(temp -> parent -> right == temp)
{
temp = temp -> parent;
// leftrotate(t);
left_rotate(root, temp -> data);
}
temp -> parent -> color = 'B';
grand -> color = 'R';
// rightrotate(g);
right_rotate(root, grand -> data);
}
}
else
{
if(grand -> left != NULL)
{
uncle = grand -> left;
if(uncle -> color=='R')
{
temp->parent->color='B';
uncle->color='B';
grand->color='R';
temp=grand;
}
}
else
{
if(temp->parent->left==temp)
{
temp=temp->parent;
// rightrotate(t);
right_rotate(root, temp->data);
}
temp->parent->color='B';
grand->color='R';
// leftrotate(g);
left_rotate(root, grand->data);
}
}
root->color='B';
}
return ;
}
// test case : N 12 8 16 5 10 14 19 4 7 9 11 13 15 17 20
// try to delete any possible nodes here.
void fixdelete(struct RBT *root,struct RBT *prev)
{// for fixing the RBT after deleting the node.
struct RBT *temp1;
while( prev != root && prev ->color=='B' )
{
if(prev -> parent -> left == prev)
{
temp1 = prev -> parent -> right;
if( temp1 -> color == 'R' )
{
temp1 -> color = 'B';
prev -> parent -> color ='R';
left_rotate( root , prev -> parent -> data);
temp1 = prev -> parent -> right;
}
if( temp1 -> right -> color == 'B' && temp1 -> left -> color == 'B' )
{
temp1 -> color='R';
prev = prev -> parent;
}
else
{
if( temp1 -> right -> color == 'B' )
{
temp1 -> left -> color == 'B';
temp1 -> color = 'R';
right_rotate( root , temp1 -> data );
temp1 = prev -> parent -> right;
}
temp1 -> color = prev -> parent -> color;
prev -> parent -> color = 'B';
temp1 -> right -> color = 'B';
left_rotate(root , prev -> parent -> data );
prev = root;
}
}
else
{
temp1 = prev -> parent -> left;
if( temp1 -> color == 'R' )
{
temp1 -> color = 'B';
prev -> parent -> color = 'R';
right_rotate( root , prev -> parent -> data);
temp1 = prev -> parent -> left;
}
if(temp1 -> left -> color=='B' && temp1 -> right -> color == 'B')
{
temp1 -> color = 'R';
prev = prev -> parent;
}
else
{
if(temp1 -> left -> color == 'B')
{
temp1 -> right -> color = 'B';
temp1 -> color = 'R';
left_rotate( root , temp1 -> data);
temp1 = prev -> parent -> left;
}
temp1 -> color = prev -> parent -> color;
prev -> parent -> color = 'B';
temp1 -> left -> color = 'B';
right_rotate(root , prev -> parent -> data);
prev = root;
}
}
prev -> color = 'B';
root -> color = 'B';
}
}
void deleteNode(struct RBT* root,int key)
{
if(root==NULL)
{
return ;
}
struct RBT *prev;
prev=root;
struct RBT *temp1=NULL;
struct RBT *temp2=NULL;
int f_state=0;
while(prev != NULL && f_state == 0)
{
if(prev -> data == key)
f_state = 1;
if( f_state == 0)
{
if( prev -> data < key)
prev=prev->right;
else
prev = prev -> left;
}
}
if(f_state == 0)
{
return ;
}
else
{
if(prev -> left == NULL || prev -> right == NULL)
temp1=prev;
else
temp1=succesor(root,key);
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 != prev)
{
prev -> color = temp1 -> color;
prev -> data = temp1 -> data;
}
if(temp1 -> color == 'B')
fixdelete(root,temp2);
}
}
int main()
{
char digit = 0;
struct RBT *root = NULL;
struct RBT * temp1 =NULL;
char temp='p';
int number;
int count =0,num;
while((digit=fgetc(stdin))!=EOF)
{
if(digit=='N' || digit =='B')
{
// if given input as N 1 2 3 4
// the values following N will be inserted
deleteTree(root);
//blackheight = 1;
root = NULL;
temp = 'p';
while(temp != '\n')
{
scanf("%d%c", &number, &temp);
if(root == NULL)
{
root = insertRBTitem(root, number, NULL);
root->color = 'B';
}
else if(root != NULL)
{
if(searchRBT(root,number)!= 1 )
{
insertRBTitem(root, number, NULL);
fixinsert(root,number);
}
}
}
}
else if(digit=='P')
{
//if input given is P
//prints output of preorder traversal along with color of each node of latest RBT inserted,
printPreOrder(root);
printf("\n");
}
else if(digit=='S')
{ // if given input as S 12
// it will search the value 12 in RBT, and will print its path,
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
printpath(root, number);
// printf("\n");
}
}while(temp != '\n');
}
else if(digit=='+')
{
// if input given + 13
// will insert this value as a node in RBT
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(root == NULL)
{
printf("element add in empty set\n");
root = insertRBTitem(root, number, NULL);
root->color = 'B';
}
else if(root != NULL)
{
if(searchRBT(root,number)!= 1 )
{
insertRBTitem(root, number, NULL);
fixinsert(root, number);
}
}
}while(temp != '\n');
}
else if(digit=='U')
{ // if input given as U 12
// it will print uncle node ( parent node's sibbling )along with its color
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
if(number == root->data)
{
printf("-1\n");
return 0;
}
uncleprinter(root,number);/*uncle printing function*/
printf("\n");
}
}while(temp != '\n');
}
else if(digit=='C')
{
// if input given as C 12
// it will print child node's along with their colors
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
childprinter(root,number);
printf("\n");
}
}while(temp != '\n');
}
else if(digit=='>')
{
// if input given as > 12
// it will print succesor of node's along with its color
scanf("%c", &temp);
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(searchRBT(root,number) == 1)
{
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
temp1 = succesor(root,number);
printf("%d %c \n",temp1->data,temp1->color);
}
}
}while(temp != '\n');
}
else if(digit=='L')
{
// if input given as L 12
// it will do left rotate along the node
scanf("%c", &temp);
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(searchRBT(root,number) == 1)
{
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
left_rotate(root,number);
//printf("%d %c \n",temp1->data,temp1->color);
}
}
}while(temp != '\n');
}
else if(digit=='R')
{
// if input given as L 12
// it will do right rotate along the node
scanf("%c", &temp);
do
{ //printf("\nhi\n");
scanf("%d", &number);
scanf("%c", &temp);
if(searchRBT(root,number) == 1)
{
if(root == NULL)
{
printf("-1, empty set\n");
}
else if(root != NULL)
{
right_rotate(root,number);
//printf("%d %c \n",temp1->data,temp1->color);
}
}
}while(temp != '\n');
}
else if(digit=='-')
{
// if input given as L 12
// it will remove the node from RBT.
do
{ //printf("\nhi\n");
//printf("%d",1);
scanf("%d", &number);
scanf("%c", &temp);
//printf("%d",2);
if(root == NULL)
{
// printf("%d",3);
printf("number cant be deleted from empty list\n");
}
else if(root != NULL)
{
//printf("%d",4);
// printf("%d hi",1);
deleteNode(root,number);
}
}while(temp != '\n');
}
}
return 0;
}
test cases inolves:
N 31 16
+ 45
S 45
S 31
+ 9
S 45
S 9
S 16
+ 18
+ 21
S 21
C 21
+ 24
S 21
C 31
C 21
S 18
- 21
S 21
S 18
C 18
- 31
C 18
C 24
P
output should be:
1 R
B
1 B
00 R
0 B
011 R
L B L B
01 B
16 R 45 B
18 R 24 R
010 R
-1
01 B
L B 24 R
L B L B
16 R 45 B
24 16 9 18 45