Help with insert/delete binary search tree

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

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.

Quote:

---

(...)then perhaps you should remove the condition, and instead add it as an assert within the loop itself.

---

I didn't understood this though...

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.

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?

Quote:

---

Originally Posted by Nazgulled

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

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

Quote:

---

Originally Posted by Nazgulled

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

Quote:

---

Originally Posted by matsp

(...)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?

Quote:

---

Originally Posted by Nazgulled

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

Quote:

---

Originally Posted by Nazgulled

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.

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

---

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

Quote:

---

Originally Posted by vart

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

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

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 :)

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

I see the problem now, but I don't know how to fix it :/