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

---

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.

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

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

---

Quote:

---

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.

Quote:

---

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.

Quote:

---

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?

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.

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

---

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.

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.

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.

Fixed it, got a working randomDelete() function that finds the node based on the key portion, then zaps it from within the function, no passing pointers and more pointers. My new deleteRandomSymmetrically, which has to toggle between predecessors and successors with each successive delete, however, doesn't work. I'm dead-tired (it's almost 2 a.m.), so maybe I'm just not seeing the solution now, but do you have any ideas?

Thanks again!

Code:

---

    template<class T>
void BinSearchTree<T>::deleteRandomSymmetrically()
{
    if(z == 1)
    {
          z++;
    }
    else if(z == 2)
    {
          z--;
    }
    int elToDelete = rand()%countEls();
    int myInt = 1;//add 1 for node since I incremented with each child access
    Queue<BinSearchNode<T>*> queue;
    BinSearchNode<T> *p = root;
    if(p != 0)
    {
        queue.enqueue(p);
        while(!queue.empty())
        {
            p = queue.dequeue();
            if(p->left != 0)
                    queue.enqueue(p->left);
                    myInt++;
            if(myInt == elToDelete)
            {
                if(z == 1)
                    {
                          if(p->right != 0)
                              p = p->right;
                          while(p != 0 && p->left != 0)
                              p = p->left;
                          delete p;   
                    }
                    else if(z == 2)
                    {
                          if(p->left != 0)
                              p = p->left;
                          while(p != 0 && p->right != 0)
                              p = p->right;
                          delete p;
                    }
               
            }
                if(p->right != 0)
                    queue.enqueue(p->right);
                    myInt++;
            if(myInt == elToDelete)
            {
                if(z == 1)
                    {
                          if(p->right != 0)
                              p = p->right;
                          while(p != 0 && p->left != 0)
                              p = p->left;
                          delete p;   
                    }
                    else if(z == 2)
                    {
                          if(p->left != 0)
                              p = p->left;
                          while(p != 0 && p->right != 0)
                              p = p->right;
                          delete p;
                    }
               
            }
        }
    }       
}

---

Hmmm, interesting, it's the same situation, the nodes that are supposed to be deleted now have a node->key value of a memory address.

Nevermind, I got it, I'll send you a PM with the code if you're interested (don't want to post it here, as it took me a WHILE to get it, and don't want my classmates doing a wholesale copy of my hard work). Thanks again for the help ;-)

-Patrick