Thread: 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!!!!!!!!
}

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.

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

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

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?

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!

So, the problem was occuring when it would take a path that lead it to an overwritten node. Interesting.

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

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.