By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,750 Members | 1,159 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,750 IT Pros & Developers. It's quick & easy.

deletes and more deletes

P: 63
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?
Mar 8 '07 #1
Share this Question
Share on Google+
7 Replies


P: 39
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.
Mar 8 '07 #2

P: 63
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?
Mar 8 '07 #3

P: 63
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!
Mar 8 '07 #4

AdrianH
Expert 100+
P: 1,251
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
Mar 8 '07 #5

P: 39
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.
Mar 8 '07 #6

P: 63
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:
Expand|Select|Wrap|Line Numbers
  1. struct node
  2. {
  3.     node(element):left(NULL),right(NULL),Object(element),ref(1);
  4.  
  5.     node * left;
  6.     node * right;
  7.  
  8.     Object item;    //Object is an arbitrary class
  9.     int ref;         //ref = number of references to this node.
  10. }
  11.  
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
Mar 8 '07 #7

P: 63
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.
Mar 8 '07 #8

Post your reply

Sign in to post your reply or Sign up for a free account.