How to properly insert/delete in a binary search tree in C?

Question

I kinda have to put my previous C questions on hold cause this one is more important now...

I have already coded the insert and delete functions on my binary search tree but the delete function is incomplete. There's a couple of things I need help in...

1) Is my insert function good or can it be improved somehow?

2) My delete function lacks the deletion of a node with both the left and right childs. I've searched a lot in the past few hours but couldn't find a proper way to do it.

2.a) How should I delete a node with 2 child nodes?

2.b) As in the first question, is the delete function good or can it be improved? This one I know it can because I'm repeating lots of code in those ifs but I don't see how can I improve it, I need help on that too.

typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;

typedef struct sClientProfile {
    char *clientName;
    int clientAge;
    int clientNIF;
} nClientProfile;

typedef struct sClientTree {
    ClientProfile clientProfile;
    char *clientName;

    ClientTree leftTree;
    ClientTree rightTree;
} nClientTree;

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
    if(!*cTree) {
     ClientTree new = (ClientTree)malloc(sizeof(nClientTree));

     if(!new) {
      perror("malloc");
     }

     new->clientName = strdup(cProfile->clientName);
     new->clientProfile = cProfile;

     new->leftTree = NULL;
     new->rightTree = NULL;

     *cTree = new;
    } else {
     if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
      addClientToTree(&(*cTree)->leftTree, cProfile);
     } else {
      addClientToTree(&(*cTree)->rightTree, cProfile);
     }
    }
}

void deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return;

    int nCompare = strcmp((*cTree)->clientName, cName);

    if(nCompare > 0) {
     deleteClientFromTree(&(*cTree)->leftTree, cName);
    } else if(nCompare < 0) {
     deleteClientFromTree(&(*cTree)->rightTree, cName);
    } else {
     if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
      ClientTree cliPtr = *cTree;

      free(cliPtr->clientProfile);
      free(cliPtr);

      cliPtr->clientProfile = NULL;
      cliPtr = NULL;

      *cTree = NULL;
     } else if(!(*cTree)->leftTree) {
      ClientTree cliPtr = *cTree;

      free(cliPtr->clientProfile);
      free(cliPtr);

      cliPtr->clientProfile = NULL;

      *cTree = (*cTree)->rightTree;
     } else if(!(*cTree)->rightTree) {
      ClientTree cliPtr = *cTree;

      free(cliPtr->clientProfile);
      free(cliPtr);

      cliPtr->clientProfile = NULL;

      *cTree = (*cTree)->leftTree;
     } else {

      // MISSING DELETE CASE

     }
    }
}

You'll probably notice but let me just make 2 remarks:

• This tree uses strings instead of the normal int representation. That's why I use strcmp() all the way, I think I'm using it right.
• I'm not using recursion, I rather pass the pointer (of a structure pointer in this case) and work with that. It looks more clean somehow and in the future I want to return a success value if a node was deleted.

UPDATE BELOW:
I've already did my iterative version of the delete function but I don't like some things about it, maybe they can be improved (or not) but I can't see how. I've also tried to code the case it was missing, deleting a node with 2 childs, but it's not working as it should...

I've commented the whole code where I think the code can be improved and where's the problem. I've also named those problems as A, B (there's no B anymore), C and D so we can reference to them easily.

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
    if(!cTree) return FALSE;

    ClientTree currPtr = *cTree;
    ClientTree prevPtr = NULL;
    int nCompare;

    while(currPtr) {
     nCompare = strcmp(currPtr->clientName, cName);

     if(nCompare > 0) {
      prevPtr = currPtr;
      currPtr = currPtr->leftTree;
     } else if(nCompare < 0) {
      prevPtr = currPtr;
      currPtr = currPtr->rightTree;
     } else {
      /*
       * A)
       * 
       * The following cases have 3 lines in common, the free()
       * calls and return statement. Is there anyway to improve
       * this code and make it more compact?
       * 
       * Of course, the printf's are to be removed...
       */
      if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
       printf("CASE #1\n");

       *cTree = NULL;

       free(currPtr->clientProfile);
       free(currPtr);

       return TRUE;
      } else if(!currPtr->leftTree || !currPtr->rightTree) {
       printf("CASE #2\n");

       if(prevPtr->leftTree == currPtr) {
        prevPtr->leftTree = currPtr->rightTree;
       } else {
        prevPtr->rightTree = currPtr->leftTree;
       }

       free(currPtr->clientProfile);
       free(currPtr);

       return TRUE;
      } else {
       printf("CASE #3\n");

       ClientTree tempPtr = currPtr->rightTree;

       while(tempPtr->leftTree) {
        tempPtr = tempPtr->leftTree;
       }

       /*
        * C)
        * 
        * This has a big problem...
        * 
        * If you take a look at the ClientProfile structure,
        * in the first post, you'll see two ints
        * (clientNIF/clientAge) and one char* (clientName).
        * 
        * The problem is that the following code line is only
        * copying the integer data, not the string. For some
        * reason, the string remains the old one.
        * 
        * I tried to use strdup() directly on clientName like:
        * currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
        * but it still doesn't work.
        * 
        * Why everything is being copied but the strings?
        */
       currPtr->clientProfile = tempPtr->clientProfile;

       /*
        * D)
        * 
        * Is there anyway to not call the function itself
        * and make the while loop once again and delete the
        * corresponding leaf?
        */
       return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
      }
     }
    }

    return FALSE;
}

Answer 1

First off, you mentioned you aren't using recursion but each function has a logical path that calls itself.

On to the questions:

1) Remove the recursion. This can get you in a lot of trouble if your tree is large enough to blow your stack. Gcc has limited support for tail recursion, but I wouldn't count on it.

2) Typically, when you delete a child with two nodes, you promote the left or right node to the position the deleted node was in. (This is a highly simplistic case, I'm assuming your tree isn't balanced)

2.b) Your delete code has some problems. I'd recommend walking through it with a few hypothetical situations. Immediately obvious to me was free'ing a pointer and then deferencing it:

free(cliPtr);

cliPtr->clientProfile = NULL;

Of course, you can always worry about style once you get the correctness thing squared away.

Answer 2

Ideally there are three cases for deletion of a node in BST:

Case 1:

X has no children: remove X

Case 2:

X has one children : Splice out X

Case 3:

X has two children : swap X with its successor and follow case #1 or #2

So for the missing delete case:

When X (node to delete) has two children, replace X with the successor of X and follow case #1 or case #2. You can also replace with its predecessor, might be a good alternative.

if ( X->left && X->right) {

NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);

}

Answer 3

When you delete a node, you have to do something about its children.

If there are no children - no problem. You just remove the node.

If there a left child, also no problem; you remove the node and move its left child into its place.

Same for the right child; just move the child into the place of the deleted node.

The problem comes when you want to delete a node which has both left and right children. You could move the left or the right child into the place of the deleted node, but what do you then do about the other child and its subtree?

Solution is this; you locate the logical successor to the node being deleted. By logical successor, I mean this; say you have a tree made of integers and you delete node with value 35, the logical successor is the next largest number. Ya? if you were doing an in-order walk, it would be the element you come to after the element you're deleting.

Now, there's a simple rule to find the logical successor; you go right one (you always have a right, because this is the case where you have two children) and then you go as far left as you can.

That element you end up at is the logical successor. It's larger than the deleted element (you went right at the start, remember?) but it's the smallest next largest element.

Now, that element ALWAYS has only one or no children - because you went left as far as you can, remember? so you can't go left any more - because there is no left - so that element has no children or just a right child and that means it falls into one of the easy-to-unlink catagories (no children or just one child). So unlinking this element is easy.

Now comes the cool bit - consider this; if that next largest element were in the same place in the tree as the element you want to delete, the tree would still be valid and correct - because everything to the left of each element is smaller, everything to the right is larger.

So what you do is this; you copy the user data in the next largest node into the node being deleted and you delete that next largest node (it has no children or just a right child, so it's easy to unlink and delete).

And that's it!

So, basically - find your logical successor, unlink him from the tree and put his user data into the element you're actually originally deleting (which you don't then delete, of course, because it's still physically part of the tree).

Answer 4

int delete_value(Tree*&root,Tree*&find,Tree*&ptr,int numb){ if(find->value==number){ //the number exist in the root,so we should find the highest value inside the right brache and replace it with the root. Tree*ptr2=NULL; Tree*ptr3=NULL;//pointer pointing to the parent of the last element of ptr2. ptr2=root->right; while(ptr2!=NULL){ ptr3=ptr2; ptr2=ptr2->left; } if(ptr2->right!=NULL){ ptr3->left=ptr2->right; } swap(ptr2->value,root->value); delete ptr2; ptr2=ptr3=NULL; }

else{
    while(find->value!=numb){
        if(find->value!=numb){
            ptr=find;
        }
        if(find->value < numb){
            find=find->right;
            return delete_value(root,find,ptr,numb);
        }
        else{
            find=find->left;
            return delete_value(root,find,ptr,numb);
        }
    }//end of while
}//end of else

//the pointer find is pointing at the element we want to delete. //the pointer ptr is pointing at the element before the one's we want to delete. //case 1:the element to delete don't have any children if(find->right==NULL && find->left==NULL){ if(ptr->left=find){ ptr->left=NULl; delete find; } else{ ptr->right=NULL; delete find; } }//end of the first case. //case 2:the element has one child it could be to the left or to the right. //a-child to the right. if( find->right!=NULL && find->left==NULL ){ Tree*ptr2=find->right; while(ptr2!=NULL){ ptr2=ptr2->left;//find the highest value in the right branche and replace it with the delete element } swap(find->value,ptr2->value); delete ptr2; ptr2=NULL; } //b-child to the left. if(find->right==NULL && find->left!=NULL){ Tree*ptr2=find->left; //check wether the find element is to the right or to the left of ptr. if(ptr->left==find){ ptr->left=ptr2; delete find; } else{ ptr->right=ptr2; delete find; } }//end of the second case.

//case3: the element has to children. if(find->right!=NULL&&find->left!=NULL){ Tree*ptr2=find->left; while(ptr2->right!=NULL){ ptr2=ptr2->right; } swap(ptr2->value,find->value); delete ptr2; ptr2=NULL; }//end of case 3. }//end of the function.