Thread: Red Black Tree Deletion

  1. #1
    Registered User
    Join Date
    Jun 2022
    Posts
    1

    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;
    }
    Last edited by Salem; 06-30-2022 at 05:54 AM. Reason: Removed redundant tags

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Red Black Tree Deletion
    By KiritoEdward202 in forum C Programming
    Replies: 0
    Last Post: 05-02-2020, 12:04 PM
  2. problem in deletion in binary search tree
    By ashutosh124 in forum C Programming
    Replies: 2
    Last Post: 12-21-2012, 05:56 AM
  3. Red black tree deletion problem
    By renz15 in forum C++ Programming
    Replies: 0
    Last Post: 03-28-2012, 03:19 AM
  4. Replies: 2
    Last Post: 03-08-2012, 06:12 PM
  5. Binary Search Tree deletion
    By gflores in forum C++ Programming
    Replies: 2
    Last Post: 09-23-2005, 06:01 PM

Tags for this Thread