Thread: Help with insert/delete binary search tree

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It looks about right (without actually testing it, it's hard to tell). I have some concerns:
    Is there any chance you end the loop because currptr == NULL? If so, you end the loop without inserting, which is probably not what you wanted. If there isn't any such chance, then perhaps you should remove the condition, and instead add it as an assert within the loop itself.

    If you do that, then you can probably make it an infinite while/for loop and put a "if (cCompare == 0) return;" just after the strcmp - since that makes it much clearer what you actually do.

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

  2. #17
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    You are right, supposing my code is working as it should and malloc/strdup do not fail, that condition will never be met because an element will always be inserted into the tree.

    (...)then perhaps you should remove the condition, and instead add it as an assert within the loop itself.
    I didn't understood this though...

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Lets just say that NULLing a pointer that is part of a struct that is being freed is like opening up a text document, typing X's over the whole thing, saving the file, putting it in the recycle bin and then emptying the bin.
    You do it only if you're really paranoid.
    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. #19
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?

  5. #20
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Nazgulled View Post
    But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?
    The only risk with a pointer that is not set to NULL is that some part of your application tries to use it, and it's been assigned for some other purpose, e.g.:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
       char *q;
       char *p = malloc(15);
       strcpy(p, "Hello, World");
       free(p);
       q = malloc(15);
       strcpy(q, "World, Hello");
       printf("%s\n", p);
       return 0;
    }
    Whilst it's not guaranteed, this most likely will print "World, Hello" - it may print "Hello, World" or some completely different thing.

    If the memory is freed, and there is no variable holding a pointer to the memory, it is not available to use [without serious tricking about - and even then, it's pretty pointless, because there is no benefit from being able to access unused memory in the current process, it will for example not allow anyone access other processes memory or gain privileges, and even if that was the case, setting the pointer itself to NULL will not help].

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

  6. #21
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    So, you're saying that even setting the pointer to NULL does not prevent some smart guy to read the data that I freed (supposing it wasn't overwritten yet) if he really wanted to?

    If that's the case, I think I see the whole picture now...

  7. #22
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Nazgulled View Post
    So, you're saying that even setting the pointer to NULL does not prevent some smart guy to read the data that I freed (supposing it wasn't overwritten yet) if he really wanted to?

    If that's the case, I think I see the whole picture now...
    Correct.

    However, that only applies within the current process - other processes (unless they have debug privileges, e.g. Admin rights or possibly running as the same user) are not able to see what's inside your process in any way.

    Setting the pointer to NULL only makes it harder to figure out where the memory was, but it doesn't make the memory itself change in any way - if you are really paranoid, clear the contents after use [but what's to stop someone with skills to access it before it's been freed?]

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

  8. #23
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by matsp View Post
    (...)are not able to see what's inside your process in any way.
    This is the only thing I still don't get. If I freed the memory block some pointer was pointing at, that memory block does not belong to my program/process anymore. And thus, other processes can access that memory block if they knew the memory address... Is this incorrect somehow?

  9. #24
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by Nazgulled View Post
    This is the only thing I still don't get. If I freed the memory block some pointer was pointing at, that memory block does not belong to my program/process anymore. And thus, other processes can access that memory block if they knew the memory address... Is this incorrect somehow?
    no, adresses are per process
    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. #25
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Nazgulled View Post
    But if I don't NULL the pointers, won't the OS or any other application be able to access the data on that memory block? It's not important for the application I'm going, but isn't that like a security risk or something?
    A pointer is essentially just a number, an address. Setting it to NULL is like scribbling over the address before shredding the piece of paper it is on (And you were going to shred it regardless).

    Even if something looked at a block of freed memory it would have little idea which parts of it were pointers and which parts weren't. It's all just random bytes as far as anything else is concerned.
    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"

  11. #26
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Ok then, thanks for all that insight on pointers.

    Now I'm having problems with the real issue on this topic... 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, C and D so we can reference to them easily.

    Code:
    bool deleteClientFromTree(ClientTree *cTree, char *cName) {
    	if(!cTree) {
    		return FALSE;
    	}
    	
    	ClientTree currPtr = *cTree;
    	ClientTree prevPtr = NULL;
    	int nCompare;
    	
    	while(1) {
    		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 5 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) {
    				printf("CASE #1: DELETE ROOT NODE\n");
    				
    				*cTree = NULL;
    
    				free(currPtr->clientProfile);
    				free(currPtr);
    				
    				return TRUE;
    			} else if(!currPtr->leftTree && !currPtr->rightTree) {
    				printf("CASE #2: DELETE LEAF (NO CHILDREN)\n");
    				
    				/*
    				 * B)
    				 * 
    				 * Any better way to merge this 2 statements into one?
    				 * 
    				 * I only need to set one of them as null depending
    				 * on which node I'm deleting, I could place an if
    				 * to check which one, but it would be almost the same
    				 * as what I'm doing now.
    				 * 
    				 * Maybe is there a better way to do this?
    				 */
    				prevPtr->leftTree = NULL;
    				prevPtr->rightTree = NULL;
    				
    				free(currPtr->clientProfile);
    				free(currPtr);
    				
    				return TRUE;
    			} else if(!currPtr->leftTree) {
    				printf("CASE #3: DELETE NODE WITH RIGHT CHILD\n");
    				
    				prevPtr->leftTree = currPtr->rightTree;
    				
    				free(currPtr->clientProfile);
    				free(currPtr);
    
    				return TRUE;
    			} else if(!currPtr->rightTree) {
    				printf("CASE #4: DELETE NODE WITH LEFT CHILD\n");
    				
    				prevPtr->rightTree = currPtr->leftTree;
    				
    				free(currPtr->clientProfile);
    				free(currPtr);
    				
    				return TRUE;
    			} else {
    				printf("CASE #5: DELETE NODE WITH 2 CHILDS\n");
    				
    				// Finds the logical successor and places it into: tempPtr
    				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);
    			}
    		}
    	}
    }

  12. #27
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    if your node is not present in the tree - your function will crash

    when you deleting leaf - why do you set to NULL both pointers of the father? you delete only one child - second is leaked

    also - how you choose what leg of the father to replace has no logic in it
    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

  13. #28
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by vart View Post
    if your node is not present in the tree - your function will crash
    You're right, I forgot about that. I replaced while(1) by while(currPtr) that should take of the problem.

    Quote Originally Posted by vart View Post
    when you deleting leaf - why do you set to NULL both pointers of the father? you delete only one child - second is leaked
    As I explained in the code, the parent will have only one child and I need to set the pointer to that child as NULL. But I don't see how can I find which node pointer (left or right) should I set as NULL and so, I set both. It will work anyway cause one of them is already NULL, the other isn't.

    Like I said, I wanted to make that in one line, better, in one statement, but I can't see how can I do it...

    Quote Originally Posted by vart View Post
    also - how you choose what leg of the father to replace has no logic in it
    This one I don't understand...

    And just so no one concentrates only in the issues pointed by vart, please note that the code blocks I commented

  14. #29
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    why do you think parent will have 1 child?
    Code:
     A
    / \
    B C
     /  \
    D   E
    if I want to delete B - parent has 2 childs, settign both pointers to NULL will leak CDE
    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

  15. #30
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    I see the problem now, but I don't know how to fix 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