Deleting from a binary search tree

This is a discussion on Deleting from a binary search tree within the C Programming forums, part of the General Programming Boards category; Hello, I've posted a few topics on these forums and have received a large amount of help. I'm winding up ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    11

    Deleting from a binary search tree

    Hello,
    I've posted a few topics on these forums and have received a large amount of help. I'm winding up the program, finally, and I've come to a huge snag. The last function I need to get working is deleting a node from a binary search tree. I understand the algorithm but i'm having really big issues implementing it in code.

    Here is the code I have, currently:
    Code:
    void removeTree(TreeT tree, TreeInfoT data)
    {
    printf("Inside removeTree. Data= %s Node=%s \n",data->name,tree->root->info->name);
    deleteNode(tree->root,data);
    }
    
    void deleteNode(TreeNodeT root,TreeInfoT data)
    {
    TreeNodeT ptr=findNode(root,data); //find the node
    printf ("inside deleteNode. Pointer from findNode=%s \n",ptr->info->name);
    if (ptr->L!=NULL && ptr->R!=NULL) //two children
    {
    	printf("Entered inside of 'Two Children' if statement \n");
    	TreeNodeT max=ptr->L; //set a pointer, max, to the node in the left tree to prepare to look
    							 // for the highest value in the left subtree
    	while (max->R !=NULL) //if the node to the right of max isn't equal to null, do the following
    		max=max->R;        //set max equal to the node to the right of it (highest value in left subtree)
    	ptr->info=max->info;  //move the info from max into ptr
    	deleteNode(ptr->L,max->info);
    }
    else
    if (ptr->L==NULL)
    {	
    	printf("Entered inside ptr->L equal to null if statement \n");
    	if (ptr->R==NULL)
    	printf ("ptr->R equals NULL \n");
    	TreeNodeT tempRight=ptr->R;
    	if (tempRight==NULL)
    	printf("tempRight equals NULL \n");
    	printf ("ptr equals %s \n",ptr->info->name);
    	ptr=ptr->R; 
    	if (ptr==NULL)
    	printf("ptr equals NULL \n");
    	free(tempRight);
    }
    else
    if (ptr->R==NULL)
    {
    	printf("Entered inside ptr->R equal to null if statement \n");
    	TreeNodeT tempLeft=ptr->L;
    	ptr=ptr->L; 
    	free(tempLeft);
    
    }
    printf("Pre-exiting function check. \n");
    if (ptr==NULL)
    printf("PTR still equals NULL \n");
    printf("Exiting Function \n");
    return;
    }
    Note: There's still some print statements in there I was using for debugging (which I finally gave up on 5 hours later). I've tested findNode multiple times outside of the function and it IS correctly finding the nodes so that's not the issue.
    Please help, anything to set me in the right direction would be amazing.
    Anthony Vitello

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You almost certainly don't want to call deleteNode recursively. You may want to call free, to get rid of the max node that you moved up in the tree, but that's it.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    11
    I'm not quite sure I understand why you shouldn't be using recursion on this as well as what I -should- be freeing.

    As it stands i'm always using the same "Tree" input for testing. I input the following characters into the tree in this order "k,d,b,a,c,g,h,s".

    If I try to remove the A (which is a leaf in this tree) all of my debugging print statements show me that the node gets set to null but when I print the tree the A shows up nice and pretty.

    If I try to remove the D it correctly sets the C over the D (putting the rightmost node of the leftmost tree in place of D) and than it recursively calls the function to delete the C starting from the node to the left of the one I was originally trying to delete (basically making that rightmost node a leaf and deleting it through the recursion). Unfortunately, when I print this tree, as well, the D is gone and replaced with a C but the other C is still in the tree.

    And, for one more weird situation, if I try to delete the G all the occurs is my cygwin client printing <null> over and over again for a few seconds before returning me to the cygwin prompt.

    Ugh i'm so lost!

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You don't want to call the function recursively because the function is "deleteNode" not "deleteNodeAndABunchOfOtherNodesAtRandom".

    When you try to delete D, it puts the C in where the D was. You NOW NO LONGER WANT TO DELETE ANYTHING, because you've already done what you were supposed to do. Use free to get rid of the extra memory where the C was (with "free(max)") and you're golden.

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    11
    Thanks a bunch!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with delete - Binary search tree
    By lazyme in forum C Programming
    Replies: 10
    Last Post: 03-21-2010, 01:19 PM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 04:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21