deletes and more deletes

[iLL]

Hello, I have crated a binary tree template for school. And in my program implements this data structure, I have to have two trees, both of which are pointing to the same data, just in different orders.

The problem is, my template takes care of deleting the information, so when I delete one node, the pointer in the other tree is now pointing to unallocated memory. So I guess my question comes down to, is it okay to say “delete node” when it is already unallocated? I know it’s okay if you say “delete” to a NULL pointer, but what about a pointer that is pointing to unallocated memory?

[lqdeffx]

pretty much, you answered your own question. You have 2 binary trees pointing at the same thing. so like an algebraic expression, what you do to one side you must do to the other. otherwise, when the unmodified binary tree goes to a pointer that is no longer valid, undefined behavior is the result. undefined behavior quite literally meaning formating a computer hard drive to quietly aborting the program. if you wonder why this is, i believe its because once you have "deleted" the allocated memory, you are telling the OS it is ok to use this memory space for anything it chooses.

[iLL]

pretty much, you answered your own question. You have 2 binary trees pointing at the same thing. so like an algebraic expression, what you do to one side you must do to the other. otherwise, when the unmodified binary tree goes to a pointer that is no longer valid, undefined behavior is the result. undefined behavior quite literally meaning formating a computer hard drive to quietly aborting the program. if you wonder why this is, i believe its because once you have "deleted" the allocated memory, you are telling the OS it is ok to use this memory space for anything it chooses.

However, when I go to traverse the tree who has a node that is pointing to unallocated momory, I’ll get a run time error when it tries to read from the data it is supposed to be there.

I need to set the other pointer to NULL, and the only way I can do that is by telling my template to remove a node, and my template states:

delete node;
node = NULL;

so.... I'll hit that delete before i hit node = NULL. And is that OK?

[iLL]

WOW! NO!!!!! I have to completely rethink this. Since that data doesn’t exist anymore, I’ll get a run time error when I go to remove it for the second time. When looking for that node to remove, it’ll try and read that unallocated memory.

Well crap. Never mind then!

[AdrianH]

WOW! NO!!!!! I have to completely rethink this. Since that data doesn’t exist anymore, I’ll get a run time error when I go to remove it for the second time. When looking for that node to remove, it’ll try and read that unallocated memory.

Well crap. Never mind then!

So you realise that you cannot delete an object that has already been deleted. Yeah that would be bad.

Use reference counting to allow for the object to be deleted multiple times until the number of references go to zero at what point it will be deleted (see boost::shared_ptr). NOTE that you cannot use this if you have an object that uses shared_ptr to zero or more chain of other objects that uses a shared_ptr back to the first (an object ownership cycle). But for what you are doing, it should be fine.

Hope this helps.


Adrian

[lqdeffx]

well dereferencing a null pointer is the least of your troubles. my experience with binary tree's is limited, but if I were in your situation... I would think of a binary tree as a triangle and would "rotate" the triangle. Thus making node->right the top dog and node->left to node->right. then create a function that would restructure my binary tree. Of course there is always google, and I'm sure other people have been in the same situation.

[iLL]

So you realise that you cannot delete an object that has already been deleted. Yeah that would be bad.

Use reference counting to allow for the object to be deleted multiple times until the number of references go to zero at what point it will be deleted (see boost::shared_ptr). NOTE that you cannot use this if you have an object that uses shared_ptr to zero or more chain of other objects that uses a shared_ptr back to the first (an object ownership cycle). But for what you are doing, it should be fine.

Hope this helps.


Adrian

Let me see if I have this straight.

I’ll make a node like:

struct node
{
    node(element):left(NULL),right(NULL),Object(element),ref(1);
 
    node * left;
    node * right;
 
    Object item;    //Object is an arbitrary class
    int ref;         //ref = number of references to this node.
}
 

And every time a pointer points to this node, then add one to ref.

Then if I go to delete the node, just set the pointer to NULL and ref--; unless reff = 1, then say delete.

Smart, Smart, Smart!!!! That’s good stuff

[iLL]

well dereferencing a null pointer is the least of your troubles. my experience with binary tree's is limited, but if I were in your situation... I would think of a binary tree as a triangle and would "rotate" the triangle. Thus making node->right the top dog and node->left to node->right. then create a function that would restructure my binary tree. Of course there is always google, and I'm sure other people have been in the same situation.

Yes! I have that figure out already. But yes, it took a little time to figure out how to keep the order of the tree while removing an object.

Thankfully, however, I don’t have to keep the tree balanced for this assignment, so I don’t have to do any rotating.