-1

So I've done quite a bit of searching around, but many of the people who have deletion problems have completely different BST implementations than I do. On this assignment, we were given a BST class with the field nodeContent, and pointers to root, leftChild, and rightChild. This week out assignment was to create a function that deletes a specified node in the tree, and then we should be able to traverse the tree to verify that the node is gone. I thought I was making good process but when I test my code, it either returns that the node has indeed been removed, but the node that I copied from, has been duplicated. Alternately, when I try to delete a note with two children, I get a segmentation fault. I am new to posting on SO, so if I did this incorrectly, I apologize. I've just been racking my brain trying to see where I went wrong! Thanks in advance. Oh yeah, and I apologize for the crazy amount of comments.. I add a lot of comments when I get stuck to try and talk myself though the steps.

            /*
            void BST::deleteNode(int el)
            Input: An integer that is to be deleted from the tree
            Output: Nothing
            Side Effect: Single node deleted and tree reordered
            */
            void BST::deleteNode(int el)
            {
              BSTNode *temp;
              BSTNode *prev;
              BSTNode *node = Root;

              while (node -> nodeContent != el && node != NULL) // start the search
              {
                // if the search is less than 
                if(el < node -> nodeContent)
                {
                  node = node -> leftChild;
                }
                else if (el > node -> nodeContent)
                {
                  node = node -> rightChild;
                }

                if (node == NULL)
                {
                  std::cout << "That item cannot be deleted, "
                              "because it doesn't exist" << std::endl;
                  return;
                }
              }
              // ok, so we found the node

              // this is if node has two children
              if (node -> leftChild != NULL && node -> rightChild != NULL)
              {
                // first, set temp to rightmost node in left subtree
                temp = node -> leftChild;
                while (temp -> rightChild != NULL)
                {
                  // set prev to the node above node (bad name resolution, I know..)
                  prev = temp;
                  temp = temp -> rightChild;
                }
                // now we have our node, temp, and prev set.
                // time to do some copying
                // first step: set prev's rightChild to NULL
                prev -> rightChild = NULL;
                // ok. now we need to check if temp has a left child
                if (temp -> leftChild != NULL)
                {
                  //if it does, set it to prev's rightChild
                  prev -> rightChild = temp -> leftChild;
                }
                // done. Now set nodes content to temps content
                node -> nodeContent = temp -> nodeContent;
                // good work. now delete temp
                delete temp;
                temp = NULL;
              }
              // this one is for deleting a node without a right child
              if (node -> rightChild == NULL && node -> leftChild != NULL)
              {
                // using temp this time as the leftChild of the node to be deleted
                temp = node -> leftChild;
                // copy the content from child to node's content
                node -> nodeContent = temp -> nodeContent;
                // george r.r. martin the heck out of temp, for his watch has ended
                delete temp;
                temp = NULL;
              }
              // now, if (soon-to-be) deleted node only has a right child
              if (node -> leftChild == NULL && node -> rightChild != NULL)
              {
                // set temp to be nodes rightChild
                temp = node -> rightChild;
                // copy content from temp to to node
                node -> nodeContent = temp -> nodeContent;
                // delete temp
                delete temp;
                temp = NULL;
              }
              // the last one should be the easiest, if the node has no children
              if (node -> leftChild == NULL && node -> rightChild == NULL)
              {
                delete node;
              } 
            }
2
  • What did you observe running your code in the debugger? Are you deleting nodes twice by chance? Did you implement copy and assignment operators correctly? Nov 2, 2015 at 19:05
  • A minimal complete example would be helpful, but the first thing I notice is that while (node -> nodeContent != el && node != NULL) can cause undefined behavior.
    – Beta
    Nov 2, 2015 at 19:35

1 Answer 1

0

You are using three if statements and not returning from any of the blocks. So, imagine that your first if statement was satisfied and that node had just one right child. This child got deleted.

Now, the code goes to the second if statement and that in turn is true! It then executes the second if block.

I hope this leads you to the answer. Also, to find where the segmentation fault occurred exactly GDB. It is an essential tool if you are coding in C++.

3
  • Good point.. I'm embarrassed that I missed that! thank you for the help! Nov 2, 2015 at 19:32
  • I only had a second to check it before class started, but I added return; right after the delete commands in hopes It would fix it.. But no luck unfortunately.. I'll have to keep messing with it but that was a good start I think Nov 2, 2015 at 21:02
  • I've never used GDB before but it seems very helpful. I'll try it soon as I get home. Thanks! Nov 2, 2015 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.