# Red black tree deletion problem

• 03-28-2012
renz15
Red black tree deletion problem
Hello, I am making a code for a red black tree. The insert is working but there's a problem in my code when it comes to deleting the node. These are the cases that work:
• Red Leaf
• The node to be deleted only has one child

The other cases don't work.

Here's my code:
Code:

``` bool isRed(node *y) {     return (y!=NIL && y->color!='B'); } bool isNull(node *x) {     return (x==NULL || x==NIL); } node* TreeSuccessor(node *z) {     if(z->rightchild!=NIL)     {         z=z->rightchild;         while(z->leftchild!=NIL)             z=z->leftchild;         return z;     }     node *y=z->parent;     while(y!=NIL && z==y->rightchild)     {         z=y;         y=y->parent;     }     return y; } int LeftRotate(node* z) {     node *y;     y=z->rightchild;     z->rightchild=y->leftchild;     if (!isNull(y->leftchild))         y->leftchild->parent=z;     y->parent=z->parent;     if(isNull(z->parent))         root=y;     else if(z==z->parent->leftchild)         z->parent->leftchild=y;     else         z->parent->rightchild=y;     y->leftchild=z;     z->parent=y;     return 0; } int RightRotate (node *z) {     node *y;     y=z->leftchild;     z->leftchild=y->rightchild;     if(!isNull(y->rightchild))         y->rightchild->parent=z;     y->parent=z->parent;     if(isNull(z->parent))         root=y;     else if(z==z->parent->rightchild)         z->parent->rightchild=y;     else         z->parent->leftchild=y;     y->rightchild=z;     z->parent=y;     return 0; } int DeleteFix(node *z) {     node *y;     while(z!=root && z->color == 'B')     {         if(z==z->parent->leftchild)         {             y=z->parent->rightchild;             if(isRed(y))             {                 y->color='B';                 z->parent->color='R';                 LeftRotate(z->parent);                 y=z->parent->rightchild;             }             if(y->leftchild->color == 'B' && y->rightchild->color == 'B')             {                 y->color='R';                 z=z->parent;             }             else if(y->rightchild->color == 'B')             {                 y->leftchild->color='B';                 y->color='R';                 RightRotate(y);                 y=z->parent->rightchild;             }             y->color=z->parent->color;             z->parent->color='B';             y->rightchild->color='B';             LeftRotate(z->parent);             z=root;         }         else         {             y=z->parent->leftchild;             if(isRed(y))             {                 y->color='B';                 z->parent->color='R';                 RightRotate(z->parent);                 y=z->parent->leftchild;             }             else if(y->leftchild->color == 'B')                 {                     y->rightchild->color='B';                     y->color='R';                     LeftRotate(y);                     y=z->parent->leftchild;                 }             }             y->color=z->parent->color;             z->parent->color='B';             y->leftchild->color='B';             RightRotate(z->parent);             z=root;     }     z->color='B';     y = NULL;     cout << root->number;     return 0; } int DeleteNode() {     cout << "\t\t========================================\n";     cout << "\t\t      R E D  B L A C K  T R E E S\n";     cout << "\t\t========================================\n";     cout << "\t\t\t\tD E L E T E\n";     cout << "\t\t----------------------------------------\n";     int number;     cout << "Please enter the number to be deleted: ";     cin >> number;     node *z;     for(z=root;z!=NIL;)     {         if(number < z->number)             z=z->leftchild;         else if(number > z->number)             z=z->rightchild;         else if(number==z->number)             break;         else if (z==NIL)         {             cout << "No such number exists.";             return 0;         }         else             return 0;     }     node *x;     node *y;     if (z->leftchild==NIL || z->rightchild==NIL)         y=z;     else         y=TreeSuccessor(z);     if(y->leftchild!=NIL)         x = y->leftchild;     else         x=y->rightchild;     x->parent=y->parent;     if(y->parent==NIL)         root=x;     else if(y==y->parent->leftchild)             y->parent->leftchild=x;     else         y->parent->rightchild=x;     if(y!=z)         z->number=y->number;     if(y->color=='B')     {             DeleteFix(x);     }     return 0; }```