Thread: Help with insert/delete binary search tree

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    158

    Help with insert/delete binary search tree

    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
    			
    		}
    	}
    }
    Last edited by Nazgulled; 03-23-2009 at 06:49 AM.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Little bump...

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Nazgulled View Post
    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)
    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"

  4. #4
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Nazgulled View Post
    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;
    }
    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"

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by iMalc View Post
    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...

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by Nazgulled View Post
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    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...

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by Nazgulled View Post
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by laserlight View Post
    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?

  12. #12
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Quote Originally Posted by laserlight View Post
    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...

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  15. #15
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  2. Binary Tree Search
    By nickname_changed in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 12:40 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread