Thread: removing node

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    5

    removing node

    i am having a little trouble removing a node with two children from a binary search tree. my algorithms kinda working in that i find a bottom left successor and swap they keys with the node im deleting but then i cant figure out how to delete this successor using my recursive implementation. I have done it before using java, but it was quite a different implementation and i can quite figure this one out.

    Code:
    struct bstnode{
       char *key;
       bst left;
       bst right;
    };
    
    bst bst_remove(bst b, char *s){
       if( b == NULL ){
          return b;
       } if( strcmp(b->key, s) == 0 ){
          if( b->left == NULL && b->right == NULL ){
             free(b->key);
             free(b);
             return NULL;
          } else if( b->left == NULL || b->right == NULL ){
             if( b->left != NULL ){
                free(b->key);
                return b->left;
             }else if( b->right != NULL ){
                free(b->key);
                return b->right;
             }
          } else{
             bst right = b->right;
             while( right->left != NULL ){
                right = right->left;
             }
             /* Need code in here to delete successor!?
                why cant i simply do it like this:
                &right = NULL; */
             strcpy(b->key,right->key);
             return b;
          }
       } else if( strcmp( b->key, s ) < 0 ){
          b->right = bst_remove(b->right,s);
       } else if( strcmp( b->key, s ) > 0 ){
          b->left = bst_remove(b->left,s);
       }
       return b;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You can do it simply, you just need to actually use C syntax (just like you did above): free(right->key) and free(right). On the other hand, you can't do that until you do the strcpy over. Also, you need to unhook that bottom node from the end of the tree (say if you had to do the ->left bit three times, so that b->right->left->left->left is your new b, you will need to fix b->right->left->left so that it doesn't have a left child anymore (since you moved it). Usually that involves keeping another pointer around at the parent of the moved node, so that you can set parent->left=NULL.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    5
    Oh ok, yeh with another pointer to the parent i can see how it can be done, but for some reason i cant quite get it right. I get a segmentation error when i try to disconnect the successor node. Can anyone please explain why?

    Code:
    bst bst_remove(bst b, char *s){
       if( b == NULL ){
          return b;
       } if( strcmp(b->key, s) == 0 ){
          if( b->left == NULL && b->right == NULL ){
             free(b->key);
             free(b);
             return NULL;
          } else if( b->left == NULL || b->right == NULL ){
             if( b->left != NULL ){
                free(b->key);
                return b->left;
             }else if( b->right != NULL ){
                free(b->key);
                return b->right;
             }
          } else{
             bst right = b->right;
             bst parent;
             while( right->left != NULL ){
                parent = right;
                right = right->left;
             }
             strcpy(b->key,right->key);
             /*parent->left = NULL; this line give me a segmentation fault*/
             free(right->key);
             free(right);
             return b;
          }
       } else if( strcmp( b->key, s ) < 0 ){
          b->right = bst_remove(b->right,s);
       } else if( strcmp( b->key, s ) > 0 ){
          b->left = bst_remove(b->left,s);
       }
       return b;
    }

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you don't ever do the while loop, parent doesn't get set to anything meaningful. Since if right->left is null, we want parent = right, you should set it such when you declare it.

    Also, something to consider: if I recall correctly, your keys are malloc'ed -- so you don't necessarily know that b->key has enough room to store right->key. You may want to free b->key and re-malloc with the right amount of room before you strcpy.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM