Help with insert/delete binary search tree

Nazgulled · 03-22-2009, 05:47 PM

I kinda needed to have this finish by now (first phase of a school project) but I wasn't able to finish it within the deadline... But I still have to do it so I can advanced to other things for the second phase and I need help with this binary search tree.

I have already coded the insert and delete functions 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.

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.

Now, my code:

Code:

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
			
		}
	}
}

Nazgulled · 03-23-2009, 07:00 PM

Little bump...

iMalc · 03-23-2009, 11:54 PM

Quote:

Originally Posted by Nazgulled

I'm not using recursion

Actually you are using recursion. In fact you are exclusively using recursion and never using iteration - there are no loops at all in the posted code.
Perhaps you meant to say that you are not using iteration?

Deletion of a node with two children is done by finding the maximum node of the left-subtree, removing that form the tree, and re-inserting it in place of the node you wish to delete.
(Or the minimum node of the right subtree)

Nazgulled · 03-24-2009, 07:26 AM

You're right... Actually, what I mean was that I wasn't using recursion in the sense of returning a value, instead, I pass the address of structure as an argument. I misunderstood what I wanted to say...

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

free(cliPtr);

cliPtr->clientProfile = NULL;

Is there anything wrong with this?

iMalc · 03-24-2009, 11:31 AM

Quote:

Originally Posted by Nazgulled

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

free(cliPtr);

cliPtr->clientProfile = NULL;

Is there anything wrong with this?

Hadn't looked close enough to notice that. Yeah that's a bad thing to do. If you're lucky it might work a few times, but then it'll go boom sooner or later. You must not access or write to a structure after it has been freed.
In this case you can just delete this line:

Code:

cliPtr->clientProfile = NULL;

There's no point setting something to NULL when it's going out of existence.

Converting tail-recursion into iteration is not particularly hard. However if the function makes two recursive calls then only one of them can be turned into iteration.

I'll illustrate how one can make a tree node counting function semi-iterative.
Double Recursion:

Code:

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
	int count = 0;
	if (head != NULL) {
		//recursively count left nodes (add one for this node)
		count += TreeCount(head->left) + 1;
		//recursively count right nodes
		count += TreeCount(head->right);
	}
	return count;
}

Semi Iterative / Semi Recursive:

Code:

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
	int count = 0;
	while (head != NULL) {
		//recursively count left nodes (add one for this node)
		count += TreeCount(head->left) + 1;
		//iteratively count right nodes
		head = head->right;
	}
	return count;
}

Nazgulled · 03-24-2009, 02:10 PM

Quote:

Originally Posted by iMalc

Hadn't looked close enough to notice that. Yeah that's a bad thing to do. If you're lucky it might work a few times, but then it'll go boom sooner or later. You must not access or write to a structure after it has been freed.
In this case you can just delete this line:

Code:

cliPtr->clientProfile = NULL;

There's no point setting something to NULL when it's going out of existence.

Hum... When I use free on something and if in the next line I try to print it's value anyways, the value will still be there, that's why I set the variable to NULL. To make sure it's cleaned.

I guess free cleans that memory block and the data will still be there until something else overwrites it and it's the day it's supposed to work, right?

Hum... After searching a bit for iteration on binary trees I found an algorithm for iterative insert, here's what I did:

Code:

void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
	if(!*cTree) {		
		*cTree = newClientTreeNode(cProfile);
		return;
	}
	
	ClientTree currPtr = *cTree;
	int nCompare;
	
	do {
		nCompare = strcmp(currPtr->clientName, cProfile->clientName);
			
		if(nCompare > 0) {
			if(!currPtr->leftTree) {
				currPtr->leftTree = newClientTreeNode(cProfile);
				return;
			} else {
				currPtr = currPtr->leftTree;
			}
		} else if(nCompare < 0) {
			if(!currPtr->rightTree) {
				currPtr->rightTree = newClientTreeNode(cProfile);
				return;
			} else {
				currPtr = currPtr->rightTree;
			}
		}
	} while(currPtr && nCompare != 0);
	
	return;
}

Code:

ClientTree newClientTreeNode(ClientProfile cProfile) {
	ClientTree newClient = malloc(sizeof(nClientTree));
	
	if(!newClient) perror("malloc");
		
	newClient->clientName = strdup(cProfile->clientName);
	
	if(!newClient->clientName) perror("strdup");
	
	newClient->clientProfile = cProfile;
	
	newClient->leftTree = NULL;
	newClient->rightTree = NULL;
	
	return newClient;
}

I guess it's ok now?

I'll try to convert my delete function into iteration and see if I can also delete a nod with 2 child's...

vart · 03-24-2009, 02:14 PM

Quote:

Originally Posted by Nazgulled

Hum... When I use free on something and if in the next line I try to print it's value anyways, the value will still be there,

How do you know it?
memory does not belongs to your program - it is returned to the memory pool...

if this free just returned the last chunk of the memory in some page - the whole page could be already returned to the OS making any address inside this page not available to the program at all.

So even read operation from this address could cause a GPF

Nazgulled · 03-24-2009, 02:15 PM

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

vart · 03-24-2009, 02:17 PM

Quote:

Originally Posted by Nazgulled

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

pure luck

**laserlight** · 03-24-2009, 02:18 PM

Quote:

Originally Posted by Nazgulled

I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

Nazgulled · 03-24-2009, 02:31 PM

Quote:

Originally Posted by laserlight

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

That's the word lol... I've read a document before on "dangling pointer" and it was somewhat bad and to set it as NULL to solve it. That's why I'm setting every pointer I free to NULL.

Normally, no, the code that follows the free() is not going to reuse that pointer because when I free() something, it's normally in linked lists or binary trees delete functions (like in the delete function in my first post).

So, should or should I not set the pointers to NULL?

Maz · 03-24-2009, 02:37 PM

Quote:

Originally Posted by laserlight

Well, then yes, it would be a good idea to set the pointer to be a null pointer if you have code that follows that will not immediately reuse the pointer. It is better to have a null pointer than a dangling pointer since you can check for a null pointer, but you cannot check for a dangling pointer.

Besides attempts to access NULL pointer usually provide far clearer trace than access for invalid, non NULL pointer...

**laserlight** · 03-24-2009, 02:42 PM

Quote:

Originally Posted by Nazgulled

Normally, no, the code that follows the free() is not going to reuse that pointer because when I free() something, it's normally in linked lists or binary trees delete functions (like in the delete function in my first post).

So, should or should I not set the pointers to NULL?

As iMalc noted, if the pointer is going to go out of scope immediately thereafter, there is no point, other than as a form of paranoid defensive programming to pre-empt modification of the code.

matsp · 03-24-2009, 02:47 PM

It is indeed fine to set a pointer to NULL immediately after it was freed. However, if you do this:

Code:

			cliPtr->clientProfile = NULL;
			cliPtr = NULL;

then you can remove the first line, since cliPtr is NULL, and there is no way to get to clientProfile by way of that pointer. [Assuming of course there are no other pointers pointing to the memory held in cliPtr - we hope so in this case, as you've just freed the memory, and using pointers after free, even to just set the pointer inside it to NULL, is a bad idea].

--
Mats

Nazgulled · 03-24-2009, 07:34 PM

I think I get the picture now, thank you...

Still, nobody commented on my attempt to do the insert function as iterative instead of recursive, I suppose there's nothing really wrong about it?

03-23-2009, 07:00 PM	#2
Nazgulled Registered User Join Date: Mar 2006 Posts: 139	Little bump...
Nazgulled is offline

03-24-2009, 07:26 AM	#4
Nazgulled Registered User Join Date: Mar 2006 Posts: 139	You're right... Actually, what I mean was that I wasn't using recursion in the sense of returning a value, instead, I pass the address of structure as an argument. I misunderstood what I wanted to say... Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it: Code: free(cliPtr); cliPtr->clientProfile = NULL; Is there anything wrong with this? Last edited by Nazgulled; 03-24-2009 at 07:30 AM.
Nazgulled is offline

03-24-2009, 02:15 PM	#8
Nazgulled Registered User Join Date: Mar 2006 Posts: 139	I don't, what I was trying to say is that if I use printf() right after free(), normally, I still see the stuff I freed...
Nazgulled is offline

03-24-2009, 02:47 PM	#14
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	It is indeed fine to set a pointer to NULL immediately after it was freed. However, if you do this: Code: cliPtr->clientProfile = NULL; cliPtr = NULL; then you can remove the first line, since cliPtr is NULL, and there is no way to get to clientProfile by way of that pointer. [Assuming of course there are no other pointers pointing to the memory held in cliPtr - we hope so in this case, as you've just freed the memory, and using pointers after free, even to just set the pointer inside it to NULL, is a bad idea]. -- Mats __________________ Compilers can produce warnings - make the compiler programmers happy: Use them! Please don't PM me for help - and no, I don't do help over instant messengers.
matsp is offline

03-24-2009, 07:34 PM	#15
Nazgulled Registered User Join Date: Mar 2006 Posts: 139	I think I get the picture now, thank you... Still, nobody commented on my attempt to do the insert function as iterative instead of recursive, I suppose there's nothing really wrong about it?
Nazgulled 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
BST (Binary search tree)	praethorian	C++ Programming	3	11-13-2005 09:11 AM
Binary Tree Search	nickname_changed	C++ Programming	7	01-13-2004 12:40 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