delete by copy only for non-children nodes?

This is a discussion on delete by copy only for non-children nodes? within the C++ Programming forums, part of the General Programming Boards category; Hello yet again! This is a different problem with the same project, so I thought I'd create a new thread. ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    121

    delete by copy only for non-children nodes?

    Hello yet again! This is a different problem with the same project, so I thought I'd create a new thread. Anyways, the project is to: create a binary tree randomly, then delete elements either assymetrically or symmetrically, and keep track of the difference between IPL and APL for the two (path lengths)- (the difference is that in assymetric deletion, successor and predecessor nodes are alternately deleted, keeping the tree in order - I used a static global int to do this, and just decrement/increment after each pass). Anyways, the problem is this: my deleteByCopy() function, which I took right out of the data structs book, will work once or twice, then kaboom! I suspected the error was: deleteByCopy() is designed for nodes with children, and with the probability of a randomly-chosen node being a leaf at about 50% in a complete tree, it was trying to perform operations which made it crash with a leaf node. Anyways, I tried to remedy that, as you can see below, by
    Code:
    if(node->left == 0 && node->right == 0)
        delete node;//also tried delete tmp
    but it didn't work (no surprise there, I figured it was a long shot). Any ideas on how I can modify this function to take into account leaf nodes, if that is, indeed, the problem? It's a little hard for me to follow.

    My deleteByCopy() function:
    Code:
    void deleteByCopying(BinSearchNode<T>*& node)
    {
    	BinSearchNode<T> *previous, *tmp = node;
    	if(node->right == 0)
    		node = node->left;
    	else if(node->left == 0)
    		node = node->right;
    	else if(node->right == 0 && node->left == 0)//my redneck attempt at a fix
    	{
             delete tmp;
        }
    	else
    	{
    		tmp = node->left;
    		previous = node;
    		while(tmp->right != 0)
    		{
    			previous = tmp;
    		    tmp = tmp->right;
    	    }
    	node->key = tmp->key;
    	if(previous == node)
    		previous->left = tmp->left;
    	else
    		previous->right = tmp->left;
    	}
    delete tmp; //pow!!!!!!!!
    }

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Suppose it is a leaf node, so left=right=null, then your flow is like so:

    Code:
    else if(node->right == 0 && node->left == 0)//my redneck attempt at a fix
    	{
    		delete tmp;
    	}
    	delete tmp; //pow!!!!!!!!
    }
    So, you end up deleting tmp twice, which you don't want. However, what really happens is that if statement never gets reached. Think about it....
    Code:
    	if(node->right == 0) // <- If node is a leaf, this will happen
    // ....
    else if (node->right == 0 && node->left == 0) // <- Unreachable branch
    The book code works perfectly. It correctly handles nodes which are leaves. There is a problem with how you are calling the deleteByCopying function.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Any ideas on how I can modify this function to take into account leaf nodes, if that is, indeed, the problem?
    The problem I see is that you aren't sure. Guessing is generally a bad idea, so you need to test thoroughly to verify your guesses before making changes to the code. Work through a few example trees on paper; ones that fail and ones that work. See if you can find the difference. Most of the time, when I have a failure in an algorithm that I'm confident about, the problem is a broken tree structure. That is, another operation in another function failed to meet an assertion or neglected to assign a null pointer and I've got something dangling.

    This might be helpful to you. I've been told that it's better at describing the details than most books.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Yeah, every other time, it's been a dangling reference (pointers in C++ are dangerous!), so I'll read this link in detail, looks like they have troubleshooting advice. Stay tuned, and thanks.

  5. #5
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Yeah, I read the page, and it is a repeat of the book, which isn't super-hard to understand. I've checked my tree functions, and I don't see any of them leaving any dangling references, so I'm just stumped. It, however, must be a non-null pointer problem, because I got an idea, and did this: if I call myTree.display() immediately after the deleteRandom() call, where I did have a value in the tree, when I use depth-first traversal to cout << node->key on every node in the tree, in the supposedly-deleted node's spot is an address value ex: 468834, instead of a value 1-10000, which my rand() function is set up to produce ( I mean that before deleteRandom() is call, tree could be, for example, 8 16 32 14 21, and then after deleteRandom called, and 16 deleted, display() will produce 8 468834 32 14 21. What could that mean? Very interesting, whatever it is. Here's how I have it set up: in int main(), (code attached as .cpp file if it will make more sense that way)
    Code:
    else if(tolower(insOrDel) == 'd')
    		    {
                     for(int u = 0; u < 100; u++)
                     {
                             myTree.deleteRandom();
                             myTree.display(); //I stuck this in to debug - see above 
                     }
    			myTree.display();
    			cout << "There are " << myTree.countEls() << " elements in the tree" << endl;
    			myTree.getIPL();
    		    }
    deleteRandom() called from int main:

    Code:
    void BinSearchTree<T>::deleteRandom()
    {     
    	vector<int> myVector;
    	Stack<BinSearchNode<T>*> pushToVector;
    	BinSearchNode<T> *p = root;
    	if(p != 0)
    	{
    		pushToVector.push(p);
    	    while(!pushToVector.empty())
    	    {
    	  	    p = pushToVector.pop();
    		    myVector.push_back(p->key);
    		    if(p->right != 0)
    			    pushToVector.push(p->right);
    		    if(p->left != 0)
    			    pushToVector.push(p->left);
    	    }
    	}
    	int elToDelete = rand()%myVector.size();
    	cout << myVector[(elToDelete-1)] << " deleted" << endl;
    void BinSearchTree<T>::deleteRandom()
    {     
    	vector<int> myVector;
    	Stack<BinSearchNode<T>*> pushToVector;
    	BinSearchNode<T> *p = root;
    	if(p != 0)
    	{
    		pushToVector.push(p);
    	    while(!pushToVector.empty())
    	    {
    	  	    p = pushToVector.pop();
    		    myVector.push_back(p->key);
    		    if(p->right != 0)
    			    pushToVector.push(p->right);
    		    if(p->left != 0)
    			    pushToVector.push(p->left);
    	    }
    	}
    	int elToDelete = rand()%myVector.size();
    	cout << myVector[(elToDelete-1)] << " deleted" << endl;
    The problem also occurs when I choose a 100-count symmetrical delete (alternate deleting predecessors and successors) from int main() :

    Code:
    template<class T>
    void BinSearchTree<T>::deleteRandomSymmetrically()
    {
         	vector<int> myVector;
    	if(!myVector.empty())
    	{
    		myVector.clear();
    	}
    	Stack<BinSearchNode<T>*> pushToVector;
    	BinSearchNode<T> *p = root;
    	if(p != 0)
    	{
    		pushToVector.push(p);
    	    while(!pushToVector.empty())
    	    {
    	  	    p = pushToVector.pop();
    		    myVector.push_back(p->key);
    		    if(p->right != 0)
    			    pushToVector.push(p->right);
    		    if(p->left != 0)
    			    pushToVector.push(p->left);
    	    }
    	}
    	int elToDelete = rand()%myVector.size();
    	int keySearch = myVector[(elToDelete-1)];
    	if(z == 1)
    	{
            z++;
            Queue<BinSearchNode<T>*> myQueue;
            BinSearchNode<T> *q = root;
    	    if(q != 0)
    	    {
    		    myQueue.enqueue(q);
    		    while(!myQueue.empty())
                {
    			    q = myQueue.dequeue();
    			    if(q->key == keySearch) //if q = rand generated el
    			    {
                        if(q->right != 0)
                        {
                            BinSearchNode<T> *y = q->right;
                            BinSearchNode<T> *x = Min(y);
                            deleteByCopying(x);//was Min(q->Right)
                            display();
                            return;
                        }
                        else if(q->right = 0)
                        {
                            deleteByCopying(q);
                        }
                    }
                }
    	    }
        }
        else if(z ==2)
        {
            z--;
            Queue<BinSearchNode<T>*> mySecondQueue;
            BinSearchNode<T> *q = root;
    	    if(q != 0)
    	    {
    		    mySecondQueue.enqueue(q);
    		    while(!mySecondQueue.empty())
                {
    			    q = mySecondQueue.dequeue();
    			    if(q->key == keySearch) //if q = rand generated el
    			    {
                        if(q->left != 0)
                        {
                            deleteByCopying(Max(q->right));
                            display();
                            return;
                        }
                        else if(q->left = 0)
                        {
                            deleteByCopying(q);
                        }
                    }
                }
    	    }
        }
    }
    Attached Files Attached Files

  6. #6
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Sorry, I cut the deleteRandom() function off, here it is:

    Code:
    template<class T>
    void BinSearchTree<T>::deleteRandom()
    {     
    	vector<int> myVector;
    	Stack<BinSearchNode<T>*> pushToVector;
    	BinSearchNode<T> *p = root;
    	if(p != 0)
    	{
    		pushToVector.push(p);
    	    while(!pushToVector.empty())
    	    {
    	  	    p = pushToVector.pop();
    		    myVector.push_back(p->key);
    		    if(p->right != 0)
    			    pushToVector.push(p->right);
    		    if(p->left != 0)
    			    pushToVector.push(p->left);
    	    }
    	}
    	int elToDelete = rand()%myVector.size();
    	cout << myVector[(elToDelete-1)] << " deleted" << endl;
    	int keySearch = myVector[(elToDelete-1)];
        Queue<BinSearchNode<T>*> myQueue;
        BinSearchNode<T> *q = root;
    	if(q != 0)
    	{
    		myQueue.enqueue(q);
    		while(!myQueue.empty())
            {
    			q = myQueue.dequeue();
    			if(q->key == keySearch)
    			{
                          cout << "here!" << endl;
                    deleteByCopying(q); //kaboom!
                }
                if(q->left != 0)
    				myQueue.enqueue(q->left);
    			if(q->right != 0)
    				myQueue.enqueue(q->right);
    		}
    	}
    	
    }

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    for example, 8 16 32 14 21, and then after deleteRandom called, and 16 deleted, display() will produce 8 468834 32 14 21. What could that mean? Very interesting, whatever it is. Here's how I have it set up: in int main(), (code attached as .cpp file if it will make more sense that way)
    I suspect that has to do with this error:
    Code:
    	int elToDelete = rand()%myVector.size();
    	cout << myVector[(elToDelete-1)] << " deleted" << endl;
    	int keySearch = myVector[(elToDelete-1)];
    The '-1' shouldn't be there.
    A%X returns a number between 0 and X-1. So by doing '-1', you're getting a number between -1 and X-2, which is insuitable for array indexing.

    That doesn't fix the main problem though I'm afraid.
    Callou collei we'll code the way
    Of prime numbers and pings!

  8. #8
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    The '-1' shouldn't be there.
    A%X returns a number between 0 and X-1. So by doing '-1', you're getting a number between -1 and X-2, which is insuitable for array indexing.
    Good eye, I had forgotten about the x-1 rule, or maybe overlooked it.

    That doesn't fix the main problem though I'm afraid.
    Any thoughts on what in the world is causing this error and strange output?

  9. #9
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Ah, I found it...
    Code:
    	Queue<BinSearchNode<T>*> myQueue;
    	BinSearchNode<T> *q = root;
    	if(q != 0)
    	{
    		myQueue.enqueue(q);
    		while(!myQueue.empty())
    		{
    			q = myQueue.dequeue();
    			if(q->key == keySearch)
    			{
    				cout << "here!" << endl;
    				deleteByCopying(q); //kaboom!
    			}
    			if(q->left != 0)
    				myQueue.enqueue(q->left);
    			if(q->right != 0)
    				myQueue.enqueue(q->right);
    		}
    	}
    This code section has a lot of problems.
    • deleteByCopying changes the value of q. What happens if q becomes NULL? q->left crashes
    • myQueue contains copies of the pointers to the tree elements. deleteByCopying only works if it is passed the actual variable.
    • You are keeping pointers in myQueue. The deleteByCopying function is potentially invalidating the memory those pointers point to.


    My suggestions:
    • Change the deleteByCopying function so that instead of being passed a BinSearchNode<T>*&, it is passed a BinSearchNode<T>**. Unless the paramater is of type const, then pass by reference is a really bad practice in C++, and will make your life harder in this project.
    • While possible to pull off, using a queue to perform the search for the element to delete is a bad idea. It's not necessary, and is more complicated than just performing a lookup-by-key in the tree.
    Callou collei we'll code the way
    Of prime numbers and pings!

  10. #10
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Wow, BinSearchNode<T>** ... this may sound ignorant, but that looks like a double pointer... what does it mean? I see what you mean about q being a pointer, insted of an actual node. Thanks for the help!

  11. #11
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    So, the problem was occuring when it would take a path that lead it to an overwritten node. Interesting.

  12. #12
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Looks crazy, but is this what you meant:
    Code:
    if(q != 0)
    	{
    		myQueue.enqueue(q);
    		while(!myQueue.empty())
            {
    			q = myQueue.dequeue();
    			if(q->key == keySearch)
    			{
                    BinSearchNode<T>* c = q;
                    deleteByCopying(c); //kaboom!
                }
                if(q->left != 0)
    				myQueue.enqueue(q->left);
    			if(q->right != 0)
    				myQueue.enqueue(q->right);
    		}
    	}

  13. #13
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Yup, it's a pointer to a pointer. You can take a pointer to pretty much anything. In practice, double pointers only come up when dealing with data structures that contain self-referential pointers.

    In C++, they tend to be pretty avoidable by properly encapsulating everything.

    EDIT: No, that change really doesn't solve the problem. Honestly, I suggest rethinking the entire code section. The queue is unnecessary for deletion, and is a big part of your problem.
    Last edited by QuestionC; 11-17-2006 at 10:58 PM.
    Callou collei we'll code the way
    Of prime numbers and pings!

  14. #14
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    How would I create a double pointer with a BinSearchNode object? I've tried several different ways, but no-go. All generate


    338 C:\Dev-Cpp\source.cpp cannot convert `BinSearchNode<int>' (or BinSearchNode<int>*to `BinSearchNode<int>**' in initialization

    This is driving me crazy, I feel like a total retard.

  15. #15
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Don't worry about the double pointers. They will bring you naught but pain and sorrows, trust me. The algorithm you are using (using a queue to iterate through every element in the tree) is basically flawed for the purposes of deletion.
    Callou collei we'll code the way
    Of prime numbers and pings!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 03:53 PM
  2. why is this prog crashing on delete?
    By Waldo2k2 in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 11:17 PM
  3. Problem need help
    By Srpurdy in forum C++ Programming
    Replies: 1
    Last Post: 07-24-2002, 01:45 PM
  4. memory management...
    By master5001 in forum Game Programming
    Replies: 24
    Last Post: 01-07-2002, 05:50 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21