Deleting a Node from a Binary Search Tree

[zackj]

Hey guys, hopefully you have have some insight on my problem. I have written a Binary Search Tree code that involves many methods (Count of the number of nodes, print in post/pre/in order, return the height, return the last string, return the first string, etc..), but I am having some difficulty Deleting a node based on 3 conditions

1. The node being deleted is a leaf
2. The node being deleted is an interior node and has a left child
3. The node being deleted is an interior node has a right child but NO left child.

In addition to my Delete method, I came up with some other methods to help aide the process. I have a SearchCurrent method that returns the pointer to the node I am deleting based on the string I pass it, a SearchParent method that returns the pointer to the Parent of the Node I'm deleting, a LargestSmallest method that returns a node pointer that is the largest node less than the data of the node I'm deleting, and a SmallestLargest method that returns a node pointer that is the smallest node greater than the data of the node I'm deleting.

Here is my Node class definition, as well as the methods I have listed, including my Delete method that needs fixing.

I think my code works fine for when ReplacementNode is a leaf (see below), however, when it is not a leaf, and I try to call my Delete recursively, I get a segmentation fault. I've worked on this single delete method for a combined 20 hours now, and I'm just missing something :(

class Node
{
   public:
	 Node*  LChild;		// the left child link portion of a node
	 string Data;		// the data portion of a node
	 Node*  RChild;		// the right child link portion of a node
      
	 // default constructor
	 Node(Node* left=NULL, string strData="", Node* right=NULL)
	 {
          LChild = left;
          Data = strData;
          RChild = right;
         }



	 // copy constructor
	 Node(Node* ptrNode)
         {
          LChild = ptrNode ->LChild;
          Data = ptrNode->Data;
          RChild = ptrNode ->RChild;
         }


};

Node* BSTree::LargestSmallest(Node* Current)
{
    if (Current->LChild == NULL)
        return Current;
    else
    {
        Current = Current->LChild;
        if (Current->RChild == NULL)
            return Current;
        else
        {
            while(Current->RChild != NULL)
                Current = Current->RChild;
            return Current;
        }
    }
}

Node* BSTree::SmallestLargest(Node* Current)
{
    if (Current->RChild == NULL)
        return Current;
    else
    {
        Current = Current->RChild;
        if (Current->LChild == NULL)
            return Current;
        else
        {
            while (Current->LChild != NULL)
                Current = Current->LChild;
            return Current;
        }
    }
}

Node *BSTree::SearchCurrent(string strData, Node* Current) throw (NonExistent)
{
  if(Current!=NULL)
  {
    if(strData == Current -> Data)
      return Current;
    if(strData < Current -> Data)
      return SearchCurrent(strData, Current->LChild);
    else
      return SearchCurrent(strData, Current->RChild);
  }
  else throw NonExistent("this is exception within Search");
}

Node *BSTree::SearchParent(string strData, Node* Current)
{
    if(strData == Current->Data)
    {
        return Current; // this is the root
    }
    else if ((Current->LChild != NULL && strData == Current->LChild->Data) ||(Current->RChild != NULL && strData == Current->RChild->Data))
    {
        return Current;
    }
    else if (strData < Current->Data)
    {
        return SearchParent(strData, Current->LChild);
    }
    else if (strData > Current->Data)
    {
        return SearchParent(strData, Current->RChild);
    }
}

void BSTree::Delete(string strData)
{
    Node* Parent;
    Node* Current;
    Node* ReplacementNode;
    Node* StartDeleteNode;
    Current = SearchCurrent(strData, Root); // Current is the node we want to delete
    Parent = SearchParent(strData, Root);
    // case 1:
    if (Current->RChild == NULL && Current->LChild == NULL) // the node returned by SearchCurrent is a leaf
    {
        if (Current->Data > Parent->Data)
        {
            Parent->RChild = NULL;
            delete Current;
        }
        else if (Current->Data < Parent->Data)
        {
            Parent -> LChild = NULL;
            delete Current;
        }
    }
    // case 2:
    else if (Current->LChild != NULL) // the node returned is an interior node
    {
        ReplacementNode = LargestSmallest(Current); // want to find the largest node less than data of Current (Current is the node we want to delete)
        Parent = SearchParent(ReplacementNode->Data, Current); // switch the Parent to the parent of the node that is now being deleted (ReplacementNode)
        Current->Data = ReplacementNode->Data;
        if (ReplacementNode->RChild == NULL && ReplacementNode->LChild == NULL) // the replacement node is a leaf
        {
            Parent->RChild = NULL;
            delete ReplacementNode;
        }
        else if(ReplacementNode->LChild != NULL) // the replacement node is not a leaf
        {
            Delete(ReplacementNode->Data);
        }

    }
        // case 3:
    else if (Current->RChild != NULL)
    {
       ReplacementNode = SmallestLargest(Current);
       Parent = SearchParent(ReplacementNode->Data, Current);
       Current->Data = ReplacementNode->Data;
       if (ReplacementNode->RChild == NULL && ReplacementNode->LChild == NULL) // the replacement node is a leaf
       {
           Parent->LChild = NULL;
           delete ReplacementNode;
       }
       else if(ReplacementNode->RChild != NULL) // the replacement node is not a leaf
       {
          
           Delete(ReplacementNode->Data);
       }

    }
}

[ne555]

IIRC if the node has both sons, you need to replace it with Largest( node->Left ); or Smallest( node->Right );
And when you delete the replacement node the operation will be trivial (is a leaf or only has one son). Handle that special case.

The problem is with the search and the replacement.

ReplacementNode = SmallestLargest(Current); // Current is an ancestor of Replacement
Current->Data = ReplacementNode->Data; // The data now is the same
Delete(ReplacementNode->Data); //Recursive call
//inside the recursive
Current = SearchCurrent(strData, Root);

Your tree has a repeated value.
Because Current is an ancestor with the same data as Replacement, it will be found first when you do the search.
So you will be trying to delete the same node, over and over again. Resulting in a stack overflow.


Also:

 // copy constructor
	 Node(Node* ptrNode)
         {
          LChild = ptrNode ->LChild;
          Data = ptrNode->Data;
          RChild = ptrNode ->RChild;
         }

The proper prototype is Node(const Node &). However, are you sure that you want a shallow copy of the sons?
You may want to add a parent pointer to the node class.