# Thread: Red Black Tree Deletion

1. ## Red Black Tree Deletion

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;
}
}
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;
}``` 2. 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

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
(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]
No Data
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]

30(b)
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. Popular pages Recent additions null, rbtnode, root, struct, void 