-
Red Black Tree Deletion
Please Help Me, When I Insert in order :
80,30,90,20,50,40,70,75,72,77,78,76
The Result of the Insert correct, but When I delete 90, The result must be :
50(Black)
30(Black)
77(Black)
20(Black)
40(Black)
72(Red)
80(Black)
[B]70(Black)
75(Black)
78(Red)
76(Red)
But, My Result The Color 80 is Red and 78 is Black, Can anyone find the mistakes on Delete function, thank you very much
Below The Code of Red Black Tree in C language :
Code:
#include<stdio.h>
#include<stdlib.h>
struct rbtNode{
int key;
char color;
struct rbtNode *left, *right,*parent;
};
struct rbtNode* root = NULL;
void leftRotate(struct rbtNode *x){
struct rbtNode *y;
y = x->right; x->right = y->left;
if( y->left != NULL)
{
y->left->parent = x;
}
y->parent = x->parent;
if( x->parent == NULL){
root = y;
}
else if((x->parent->left!=NULL) && (x->key == x->parent->left->key))
{
x->parent->left = y;
}
else x->parent->right = y;
y->left = x; x->parent = y; return;
}
void rightRotate(struct rbtNode *y){
struct rbtNode *x;
x = y->left;
y->left = x->right;
if ( x->right != NULL)
{
x->right->parent = y;
}
x->parent = y->parent;
if( y->parent == NULL)
{
root = x;
}
else if((y->parent->left!=NULL)&& (y->key == y->parent->left->key))
{
y->parent->left = x;
}
else
y->parent->right = x;
x->right = y; y->parent = x;
return;
}
void colorinsert(struct rbtNode *z){
struct rbtNode *y=NULL;
while ((z->parent != NULL) && (z->parent->color == 'r'))
{
if ((z->parent->parent->left != NULL) && (z->parent->key == z->parent->parent->left->key))
{
if(z->parent->parent->right!=NULL)
y = z->parent->parent->right;
if ((y!=NULL) && (y->color == 'r'))
{
z->parent->color = 'b';
y->color = 'b';
z->parent->parent->color = 'r';
if(z->parent->parent!=NULL)
z = z->parent->parent;
}
else
{
if ((z->parent->right != NULL) && (z->key == z->parent->right->key))
{
z = z->parent;
leftRotate(z);
}
z->parent->color = 'b';
z->parent->parent->color = 'r';
rightRotate(z->parent->parent);
}
}
else
{
if(z->parent->parent->left!=NULL)
y = z->parent->parent->left;
if ((y!=NULL) && (y->color == 'r'))
{
z->parent->color = 'b';
y->color = 'b';
z->parent->parent->color = 'r';
if(z->parent->parent!=NULL)
z = z->parent->parent;
}
else
{
if ((z->parent->left != NULL) && (z->key == z->parent->left->key))
{
z = z->parent;
rightRotate(z);
}
z->parent->color = 'b';
z->parent->parent->color = 'r';
leftRotate(z->parent->parent);
}
}
}
root->color = 'b';
}
void inorderTree(struct rbtNode* root){
struct rbtNode* temp = root;
if (temp != NULL)
{
inorderTree(temp->left);
printf(" %d-%c ",temp->key,temp->color);
inorderTree(temp->right);
}
return;
}
void postorderTree(struct rbtNode* root){
struct rbtNode* temp = root;
if (temp != NULL)
{
postorderTree(temp->left);
postorderTree(temp->right);
printf(" %d-%c ",temp->key,temp->color);
}
return;
}
void traversal(struct rbtNode* root){
if (root != NULL)
{
printf("root is %d- %c",root->key,root->color);
printf("\nInorder tree traversal\n");
inorderTree(root);
printf("\npostorder tree traversal\n");
postorderTree(root);
}
return;
}
int search(int val){
struct rbtNode* temp = root;
int diff;
while (temp != NULL)
{
diff = val - temp->key;
if (diff > 0)
{
temp = temp->right;
}
else if (diff < 0)
{
temp = temp->left;
}
else
{
printf("Search Element Found!!\n");
return 1;
}
}
//printf("Given Data Not Found in RB Tree!!\n");
return 0;
}
void insert(int val){
struct rbtNode *x, *y;
struct rbtNode *z = (struct rbtNode*)malloc(sizeof(struct rbtNode));
z->key = val;
z->left = NULL;
z->right = NULL;
z->color = 'r';
x=root;
if(search(val)==1)
{
printf("\nEntered element already exists in the tree\n");
return;
}
if ( root == NULL )
{
root = z;
root->color = 'b';
return;
}
while ( x != NULL)
{
y = x;
if ( z->key < x->key)
{
x = x->left;
}
else
x = x->right;
}
z->parent = y;
if ( y == NULL)
{
root = z;
}
else if( z->key < y->key )
{
y->left = z;
}
else{
y->right = z;
}
colorinsert(z);
return;
}
struct rbtNode* min(struct rbtNode *x){
while (x->left)
{
x = x->left;
}
return x;
}
struct rbtNode* successor(struct rbtNode *x){
rbtNode *y=NULL;
if(x->left!=NULL)
{
y=x->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=x->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}
void colordelete(struct rbtNode *x){
while (x != root && x->color == 'b')
{
struct rbtNode *w = NULL;
if ((x->parent->left!=NULL) && (x == x->parent->left))
{
w = x->parent->right;
if ((w!=NULL) && (w->color == 'r'))
{
w->color = 'b';
x->parent->color = 'r';
leftRotate(x->parent);
w = x->parent->right;
}
if ((w!=NULL) && (w->right!=NULL) && (w->left!=NULL) && (w->left->color == 'b') && (w->right->color == 'b'))
{
w->color = 'r';
x = x->parent;
}
else if((w!=NULL) && (w->right->color == 'b'))
{
w->left->color = 'b';
w->color = 'r';
rightRotate(w);
w = x->parent->right;
}
if(w!=NULL)
{
w->color = x->parent->color;
x->parent->color = 'b';
w->right->color = 'b';
leftRotate(x->parent);
x = root;
}
}
else if(x->parent!=NULL)
{
w = x->parent->left;
if ((w!=NULL) && (w->color == 'r'))
{
w->color = 'b';
x->parent->color = 'r';
leftRotate(x->parent);
if(x->parent!=NULL){
w = x->parent->left;
}
}
if ((w!=NULL) && (w->right!=NULL) && (w->left!=NULL) && (w->right->color == 'b') && (w->left->color == 'b'))
{
x = x->parent;
}
else if((w!=NULL) && (w->right!=NULL) && (w->left!=NULL) && (w->left->color == 'b'))
{
w->right->color = 'b';
w->color = 'r';
rightRotate(w);
w = x->parent->left;
}
if(x->parent!=NULL)
{
w->color = x->parent->color;
x->parent->color = 'b';
}
if(w->left!=NULL)
w->left->color = 'b';
if(x->parent !=NULL){
leftRotate(x->parent);
}
x = root;
}
}
x->color = 'b';
}
struct rbtNode* deleteNode(int var){
struct rbtNode *x = NULL, *y = NULL, *z;
z=root;
if((z->left ==NULL ) &&(z->right==NULL) && (z->key==var))
{
root=NULL;
printf("\nRBTREE is empty\n");
return 0;
}
while(z->key !=var && z!=NULL)
{
if(var < z->key){
z=z->left;
}
else{
z=z->right;
}
if(z== NULL)
return 0;
}
if((z->left==NULL)||(z->right==NULL))
{
y = z;
}
else
{
y = successor(z);
}
if (y->left!=NULL)
{
x = y->left;
}
else
{
if(y->right !=NULL)
x = y->right;
}
if((x!=NULL) && (y->parent !=NULL))
x->parent = y->parent;
if ((y !=NULL) && (x!=NULL) && (y->parent==NULL))
{
root=x;
}
else if (y == y->parent->left)
{
y->parent->left = x;
}
else
{
y->parent->right = x;
}
if (y != z)
{
z->key = y->key;
}
if ((y!=NULL) && (x!=NULL) && (y->color == 'b'))
{
colordelete(x);
}
return y;
}
void printTree(struct rbtNode *root, int space)
{
if (root == NULL)
{
return;
}
else
{
// printf("\n");
space += 8;
printTree(root->right, space);
printf("\n");
for (int i = 8; i < space; i++)
printf(" ");
printf("%d(%c)", root->key,root->color);
printTree(root->left, space);
}
}
void print(struct rbtNode *root)
{
if(root==NULL)
{
printf("No Data");
}
else
{
printTree(root, 0);
}
}
int main(){
int choice,val,data,var,fl=0;
while(1)
{
system("cls");
print(root);
printf("\nRed Black Tree Menu - \nEnter your choice :\n1:Insert \n2:Delete \n3:Search \n4:Traversal \n5:Exit\n");
scanf("%d",&choice);fflush(stdin);
switch(choice)
{
case 1:
printf("Enter the integer you want to add : ");
scanf("%d",&val);fflush(stdin);
insert(val);
//getchar();
break;
case 2:
printf("Enter the integer you want to delete : ");
scanf("%d",&val);fflush(stdin);
deleteNode(val);
//getchar();
break;
case 3:
printf("Enter search element \n");
scanf("%d",&val);fflush(stdin);
search(val);
//getchar();
break;
case 4:
traversal(root);
//print(root);
getchar();
break;
case 5:
fl=1;
break;
default:
printf("\nInvalid Choice\n");
}
if(fl==1){
break;}
}
return 0;
}
-
The first thing might be to fix all the compilation errors.
It might look like C, but you need a C++ compiler to compile it.
Code:
$ gcc -g bar.c
bar.c: In function ‘successor’:
bar.c:235:5: error: unknown type name ‘rbtNode’; use ‘struct’ keyword to refer to the type
235 | rbtNode *y=NULL;
| ^~~~~~~
| struct
bar.c:238:11: warning: assignment to ‘int *’ from incompatible pointer type ‘struct rbtNode *’ [-Wincompatible-pointer-types]
238 | y=x->left;
| ^
bar.c:239:17: error: request for member ‘right’ in something not a structure or union
239 | while(y->right!=NULL)
| ^~
bar.c:240:18: error: request for member ‘right’ in something not a structure or union
240 | y=y->right;
| ^~
bar.c:244:11: warning: assignment to ‘int *’ from incompatible pointer type ‘struct rbtNode *’ [-Wincompatible-pointer-types]
244 | y=x->right;
| ^
bar.c:245:17: error: request for member ‘left’ in something not a structure or union
245 | while(y->left!=NULL)
| ^~
bar.c:246:18: error: request for member ‘left’ in something not a structure or union
246 | y=y->left;
| ^~
bar.c:248:13: warning: returning ‘int *’ from a function with incompatible return type ‘struct rbtNode *’ [-Wincompatible-pointer-types]
248 | return y;
| ^
$ gcc -xc++ -g bar.c
Does this work?
Insert in order : 30
delete 30
What about this?
Insert in order : 30,60
delete 30
Or this?
Insert in order : 30,60
delete 60
In other words, what is the smallest test case you can find that causes a problem.
When you find one, run that case in the debugger.
Code:
$ gdb -q ./a.out
Reading symbols from ./a.out...
(gdb) b deleteNode
Breakpoint 1 at 0x1d4e: file bar.c, line 327.
(gdb) run
Starting program: ./a.out
[Detaching after vfork from child process 57533]
sh: 1: cls: not found
No Data
Red Black Tree Menu -
Enter your choice :
1:Insert
2:Delete
3:Search
4:Traversal
5:Exit
1
Enter the integer you want to add : 30
[Detaching after vfork from child process 57538]
sh: 1: cls: not found
30(b)
Red Black Tree Menu -
Enter your choice :
1:Insert
2:Delete
3:Search
4:Traversal
5:Exit
2
Enter the integer you want to delete : 30
Breakpoint 1, deleteNode (var=32767) at bar.c:327
327 struct rbtNode* deleteNode(int var){
(gdb) bt
#0 deleteNode (var=32767) at bar.c:327
#1 0x0000555555556130 in main () at bar.c:441
(gdb) s
328 struct rbtNode *x = NULL, *y = NULL, *z;
(gdb)
329 z=root;
(gdb)
331 if((z->left ==NULL ) &&(z->right==NULL) && (z->key==var))
(gdb) p *z
$1 = {key = 30, color = 98 'b', left = 0x0, right = 0x0, parent = 0x0}
When a variable doesn't contain what you expect, or a branch is taken that you don't expect, then you've found a bug.
Whether that bug is in the code, or a bug in your understanding of what the problem is remains to be determined.