Help with delete

lazyme · 03-20-2010, 06:31 PM

I need help with the delete operation on a binary search tree. The delete operation works fine for leaf nodes and nodes with one child. However, it does not work fine with nodes with 2 childs.

Here's the code

Code:

#include<stdio.h>
#include<malloc.h>

struct node
{
	int data;
	struct node *leftChild;
	struct node *rightChild;
};

int insertNode( struct node**, int );
void displayTree( struct node** );
int findNode( struct node**, int );
int deleteNode( struct node**, int );
void deleteFromTree( struct node** );

int main()
{
	int flag = 1;
	int choice = 0;
	int retVal = 0;
	int nodeValue;
	struct node *rootNode = NULL;

	printf("\n\n");

	while( flag )
	{
		printf("\n1 : Insert element in tree");
		printf("\n2 : Display elements in tree");
		printf("\n3 : Find element in tree");
		printf("\n4 : Delete element from tree");
		printf("\n5 : Exit");
		printf("\n\nPlease enter a choice : ");

		scanf_s("%d", &choice);

		switch( choice )
		{
		case 1 :printf("Enter the value to insert : "); 
				scanf_s("%d", &nodeValue);
				retVal = insertNode( &rootNode, nodeValue );
				break;

		case 2 :displayTree( &rootNode );
				break;

		case 3 :printf("Enter the element to find : "); 
				scanf_s("%d", &nodeValue);
				retVal = findNode( &rootNode, nodeValue );
				if(retVal == 1)
					printf("\nFound!!\n");
				else
					printf("\nNot Found!!\n");
				break;

		case 4 :printf("Enter the element to delete : "); 
				scanf_s("%d", &nodeValue);
				retVal = deleteNode( &rootNode, nodeValue );
				if(retVal == 1)
					printf("\nDeleted!!\n");
				else
					printf("\nNot Found!!\n");
				break;

		case 5 :flag = 0;
				break;

		default : printf( "Please insert a valid choice" );
		}
	}

	return 0;
}

int findNode( struct node **rootNode, int nodeValue )
{
	struct node* currentNode = *rootNode;
	int found = 0;

	while(!found && currentNode != NULL)
	{
		if( currentNode->data == nodeValue )
			return found = 1;
		else if( currentNode->data > nodeValue )
			currentNode = currentNode->leftChild;
		else
			currentNode = currentNode->rightChild;
	}

	return found;
}

int deleteNode( struct node **rootNode, int nodeValue )
{
	struct node* currentNode = *rootNode;
	struct node* trailNode = NULL; 
	int found = 0;

	while(!found && currentNode != NULL)
	{
		if( currentNode->data == nodeValue )
			found = 1;
		else
		{
			trailNode = currentNode;
			if( currentNode->data > nodeValue )
				currentNode = currentNode->leftChild;
			else
				currentNode = currentNode->rightChild;
		}
	}

	if(found == 1)
	{
		if( trailNode == NULL )
			deleteFromTree( &currentNode );
		else if( trailNode->data > nodeValue )
			deleteFromTree( &trailNode->leftChild );
		else
			deleteFromTree( &trailNode->rightChild );
	}

	return found;
}

void deleteFromTree( struct node **nodeToDelete )
{
	struct node* tempNode = NULL;
	struct node* currentNode = *nodeToDelete;
	struct node* trailNode = NULL;

	if( (*nodeToDelete)->leftChild == NULL && (*nodeToDelete)->rightChild == NULL )
	{
		tempNode = *nodeToDelete;
		*nodeToDelete = NULL;
		free( tempNode );
	}
	else if( (*nodeToDelete)->leftChild == NULL )
	{
		tempNode = *nodeToDelete;
		*nodeToDelete = (*nodeToDelete)->rightChild;
		free( tempNode );
	}
	else if( (*nodeToDelete)->rightChild == NULL )
	{
		tempNode = *nodeToDelete;
		*nodeToDelete = (*nodeToDelete)->leftChild;
		free( tempNode );
	}
	else
	{
		currentNode = currentNode->leftChild;

		while( currentNode != NULL )
		{
			trailNode = currentNode;
			currentNode = currentNode->rightChild;
		}

		(*nodeToDelete)->data = trailNode->data;
		tempNode = trailNode;
		trailNode = trailNode->leftChild;
		free(tempNode);
	}
}

int insertNode( struct node **rootNode, int nodeValue )
{
	struct node *newNode = NULL;
	struct node *currentNode = NULL;
	struct node *trailNode = NULL;

	int retVal = 0;
	 
	newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = nodeValue;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;

	if(*rootNode == NULL)
	{
		*rootNode = newNode;
		retVal = 1;
	}
	else
	{
		currentNode = currentNode->leftChild;
		printf( "\ncurrentnode data = %d", currentNode->data );
		while( currentNode->rightChild != NULL )
		{
			trailNode = currentNode;
			currentNode = currentNode->rightChild;
		}

		(*nodeToDelete)->data = currentNode->data;
		if( trailNode == NULL )
			(*nodeToDelete)->leftChild = currentNode->leftChild;
		else
			trailNode->rightChild = currentNode->leftChild;
		free(currentNode);
	}
	
	return retVal;
}

void displayTree( struct node **rootNode )
{
	struct node* currentNode = NULL;
	
 	if( *rootNode != NULL )
	{	
		currentNode = *rootNode;
		displayTree( &currentNode->leftChild );
		printf("%d\t", currentNode->data);
		displayTree( &currentNode->rightChild );
	}
}

Thanks

claudiu · 03-20-2010, 07:53 PM

To be honest I don't think any of the deletes work.

You are doing:

Code:

tempNode = *nodeToDelete; /* tempNode is now pointing to nodeToDelete */
*nodeToDelete = NULL; /* tempNode is also now pointing to NULL*/
free(tempNode); /* free(NULL)!!!!!!!! */

iMalc · 03-20-2010, 08:29 PM

Quote:

Originally Posted by claudiu

To be honest I don't think any of the deletes work.

You are doing:

Code:

tempNode = *nodeToDelete; /* tempNode is now pointing to nodeToDelete */
*nodeToDelete = NULL; /* tempNode is also now pointing to NULL*/
free(tempNode); /* free(NULL)!!!!!!!! */

No, that code does not do what you are thinking. nodeToDelete does not point to tempNode and thus cannot cause tempNode to become NULL on the second line above. Thus it would not always be freeing NULL.
You're still new to C, and probably haven't written a binary tree deletion function yourself yet. Wait until you've done so before you try helping others to do the same huh?

iMalc · 03-20-2010, 08:35 PM

It looks like in the two-children case, you're trying to move the data instead of relinking the nodes. Don't be inconsistent, they should all be done the same way. Once you've found the rightmost node of the leftmost subtree, detach that node from where it is in the tree, then link that node in where the one you want to delete was.

The thing that makes it much easier is if you make removeRightmostFromTree a separate function, and get that fully working on its own before you use it from within the deleteFromTree.

claudiu · 03-20-2010, 09:39 PM

Quote:

Originally Posted by iMalc

No, that code does not do what you are thinking. nodeToDelete does not point to tempNode and thus cannot cause tempNode to become NULL on the second line above. Thus it would not always be freeing NULL.
You're still new to C, and probably haven't written a binary tree deletion function yourself yet. Wait until you've done so before you try helping others to do the same huh?

You are correct. That doesn't even make any sense to me now that I read it again. Sorry for any confusion created as a result of my bad advice. I actually have been programming in C for a while now, it's probably the fatigue of working on a deadline that made me state such silly things.

lazyme · 03-20-2010, 09:42 PM

I found there was an error with my relinking and the nodes with one children were not getting relinked at all.

I managed to fix some bugs and the delete works fine now for nodes with 1 child and 2 children.

Code:

void deleteFromTree( struct node **nodeToDelete )
{
	struct node* tempNode = NULL;
	struct node* currentNode = *nodeToDelete;
	struct node* trailNode = NULL;

	if( (*nodeToDelete)->leftChild == NULL && (*nodeToDelete)->rightChild == NULL )
	{
		tempNode = *nodeToDelete;
		*nodeToDelete = NULL;
		free( tempNode );
	}
	else if( (*nodeToDelete)->leftChild == NULL )
	{
		tempNode = (*nodeToDelete)->rightChild;
		(*nodeToDelete)->data = tempNode->data;
		(*nodeToDelete)->rightChild = tempNode->rightChild;
		free( tempNode );
	}
	else if( (*nodeToDelete)->rightChild == NULL )
	{
		tempNode = (*nodeToDelete)->leftChild;
		(*nodeToDelete)->data = tempNode->data;
		(*nodeToDelete)->leftChild = tempNode->leftChild;
		free( tempNode );
	}
	else
	{
		currentNode = currentNode->leftChild;
		printf( "\ncurrentnode data = %d", currentNode->data );
		while( currentNode->rightChild != NULL )
		{
			trailNode = currentNode;
			currentNode = currentNode->rightChild;
		}

		(*nodeToDelete)->data = currentNode->data;
		if( trailNode == NULL )
			(*nodeToDelete)->leftChild = currentNode->leftChild;
		else
			trailNode->rightChild = currentNode->leftChild;
		free(currentNode);
	}
}

However, there are still some bug. When i delete the final root node and try to display the tree, the program crashes.

Also sometimes deleting one node causes a whole chain of nodes to detach from the tree.

vart · 03-20-2010, 10:17 PM

Code:

else if( (*nodeToDelete)->leftChild == NULL )
	{
		tempNode = (*nodeToDelete)->rightChild;
		(*nodeToDelete)->data = tempNode->data;
		(*nodeToDelete)->rightChild = tempNode->rightChild;
		free( tempNode );
	}

what about tempnode->leftchild? you just loose it?

lazyme · 03-20-2010, 10:44 PM

^^
Thanks for pointing out the mistake. The delete works just fine now.

Code:

else if( (*nodeToDelete)->leftChild == NULL )
	{
		tempNode = (*nodeToDelete)->rightChild;
		(*nodeToDelete)->data = tempNode->data;
		(*nodeToDelete)->rightChild = tempNode->rightChild;
		(*nodeToDelete)->leftChild = tempNode->leftChild;
		free( tempNode );
	}

I think it would have been easier if I had the parent of the node I wanted to delete and simply linked it as parentNode->leftChild = (*nodeToDelete)->rightChild

Also, after deleting the last node of the binary tree, I get an exception when I try to print the tree. I know this is because the memory has been freed but is there a way I can avoid this exception.

iMalc · 03-21-2010, 12:50 AM

[quote=lazyme;931500Also, after deleting the last node of the binary tree, I get an exception when I try to print the tree. I know this is because the memory has been freed but is there a way I can avoid this exception.[/QUOTE]No, it can only mean that your delete function is still broken. I don't have time to help now, but you could try my earlier advice.

lazyme · 03-21-2010, 09:17 AM

The delete works fine now for every node other than the last node in the tree. Even for the last node, the node is deleted however the memory pointed to by the rootNode struct is freed.

For the last node when I do

Code:

tempNode = *nodeToDelete;
		*nodeToDelete = NULL;
		free( tempNode );

The *rootNode variable is no longer accessible and in the displayTree() function when the condition if( *rootNode != NULL ) is checked, it throws an exception.

How can I get around this problem?

iMalc · 03-21-2010, 12:19 PM

Oh, so you're using a sentinel node and it's getting deleted?
Maybe you could add special checks for the sentinel node. Hmm I guess that would increase the parameter counts somewhere.
I don't have this problem in my own tree implementations. Perhaps I'll make them available in my website.

03-20-2010, 07:53 PM	#2
claudiu Registered User Join Date: Feb 2010 Location: London, United Kingdom Posts: 1,062	To be honest I don't think any of the deletes work. You are doing: Code: tempNode = nodeToDelete; / tempNode is now pointing to nodeToDelete / nodeToDelete = NULL; /* tempNode is also now pointing to NULL/ free(tempNode); / free(NULL)!!!!!!!! */
claudiu is offline

03-20-2010, 08:35 PM	#4
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 3,135	It looks like in the two-children case, you're trying to move the data instead of relinking the nodes. Don't be inconsistent, they should all be done the same way. Once you've found the rightmost node of the leftmost subtree, detach that node from where it is in the tree, then link that node in where the one you want to delete was. The thing that makes it much easier is if you make removeRightmostFromTree a separate function, and get that fully working on its own before you use it from within the deleteFromTree. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
iMalc is offline

03-20-2010, 10:17 PM	#7
vart CSharpener Join Date: Oct 2006 Posts: 5,556	Code: else if( (nodeToDelete)->leftChild == NULL ) { tempNode = (nodeToDelete)->rightChild; (nodeToDelete)->data = tempNode->data; (nodeToDelete)->rightChild = tempNode->rightChild; free( tempNode ); } what about tempnode->leftchild? you just loose it? __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is offline

03-20-2010, 10:44 PM	#8
lazyme Apprentice Join Date: Oct 2006 Location: LA Posts: 50	^^ Thanks for pointing out the mistake. The delete works just fine now. Code: else if( (nodeToDelete)->leftChild == NULL ) { tempNode = (nodeToDelete)->rightChild; (nodeToDelete)->data = tempNode->data; (nodeToDelete)->rightChild = tempNode->rightChild; (nodeToDelete)->leftChild = tempNode->leftChild; free( tempNode ); } I think it would have been easier if I had the parent of the node I wanted to delete and simply linked it as parentNode->leftChild = (nodeToDelete)->rightChild Also, after deleting the last node of the binary tree, I get an exception when I try to print the tree. I know this is because the memory has been freed but is there a way I can avoid this exception.
lazyme is offline

03-21-2010, 12:50 AM	#9
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 3,135	[quote=lazyme;931500Also, after deleting the last node of the binary tree, I get an exception when I try to print the tree. I know this is because the memory has been freed but is there a way I can avoid this exception.[/QUOTE]No, it can only mean that your delete function is still broken. I don't have time to help now, but you could try my earlier advice. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
iMalc is offline

03-21-2010, 09:17 AM	#10
lazyme Apprentice Join Date: Oct 2006 Location: LA Posts: 50	The delete works fine now for every node other than the last node in the tree. Even for the last node, the node is deleted however the memory pointed to by the rootNode struct is freed. For the last node when I do Code: tempNode = nodeToDelete; nodeToDelete = NULL; free( tempNode ); The rootNode variable is no longer accessible and in the displayTree() function when the condition if( rootNode != NULL ) is checked, it throws an exception. How can I get around this problem?
lazyme is offline

03-21-2010, 12:19 PM	#11
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 3,135	Oh, so you're using a sentinel node and it's getting deleted? Maybe you could add special checks for the sentinel node. Hmm I guess that would increase the parameter counts somewhere. I don't have this problem in my own tree implementations. Perhaps I'll make them available in my website. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
C++ Binary Search Tree	dookie	C++ Programming	5	05-10-2008 04:35 PM
BST (Binary search tree)	praethorian	C++ Programming	3	11-13-2005 09:11 AM
Request for comments	Prelude	A Brief History of Cprogramming.com	15	01-02-2004 10:33 AM
Binary Search Tree, Inserting node	cheryl_li	C Programming	1	09-13-2003 03:53 AM
BST/Red and Black Tree	ghettoman	C++ Programming	0	10-24-2001 10:45 PM