1,105,334 Community Members

Binary Search Tree - how to remove root

Member Avatar
cjjack88
Newbie Poster
17 posts since Oct 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi, I am doing an assignment about binary search tree. I have problem with remove the root in binary tree. When i remove the root of the binary tree and I view the binary tree in In-Order Traversal, my program will stop running.

void myCarSystem::remove(string m)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL)
    {
         if(curr->Model.compare(m) == 0)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(m.compare(curr->Model) > 0)
                curr = curr->right;
             else
                curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Data not found! "<<endl;
        return;
    }

    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // left child present, no right child
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

		 //We're looking at a leaf node
		 if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
		 		 delete curr;
		 		 return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }

                curr->Model = lcurr->Model;

                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->Model = tmp->Model;
               curr->right = tmp->right;
               delete tmp;
           }

        }
		 return;
    }

}

Please give some guild to me. Thank you.
Cjjack88

Member Avatar
Tom Gunn
Practically a Master Poster
681 posts since Jun 2009
Reputation Points: 1,164 [?]
Q&As Helped to Solve: 138 [?]
Skill Endorsements: 11 [?]
 
2
 

When i remove the root of the binary tree and I view the binary tree in In-Order Traversal, my program will stop running.

Then you are not resetting the links the way they should be. Removing the root means replacing the root with either the inorder predecessor or successor. Something like this:

Original:
    D
 B     F
A C   E G

Delete the root:
    *
 B     F
A C   E G

Make the inorder predecessor the root:
    C
 B     F
A *   E G

Delete the inorder predecessor:
    C
 B     F
A     E G

That behavior should fall out of your deletion algorithm because it is the same as the two child case for any node. But you also need to reset the root pointer. In the example above, if root still points to D after the algorithm finishes, the tree will be broken. So at the end, the address of C should be assigned to root to finish things up, but only if it was D that was deleted. That is an easy test because parent will be NULL if the root has a matching value.

Member Avatar
cjjack88
Newbie Poster
17 posts since Oct 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Thank you for reply, i need some time to understand it. If i just have 3 data in the tree, eg: 1, 2 and 3, and i remove 1 in thee, should 3 become the new root in this tree?

Member Avatar
Tom Gunn
Practically a Master Poster
681 posts since Jun 2009
Reputation Points: 1,164 [?]
Q&As Helped to Solve: 138 [?]
Skill Endorsements: 11 [?]
 
0
 

If i just have 3 data in the tree, eg: 1, 2 and 3, and i remove 1 in thee, should 3 become the new root in this tree?

If 1 is the root, then either 2 or 3 could be the new root. You can pick whether the inorder predecessor or successor becomes the new root. But it is not as easy as just making the root's immediate left or right child the new root because you still have to maintain the binary search invariant that an inorder traversal produces a sequence that is sorted in ascending order.

Member Avatar
cjjack88
Newbie Poster
17 posts since Oct 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

ok, I try to code it 1st....
Thank you..

Member Avatar
desire_963
Newbie Poster
1 post since Nov 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

thankssssssssssss alottttttt

Member Avatar
troyduff281
Newbie Poster
1 post since Jan 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

pardon me...what do u mean by, chkr, lcurrp, tmp, curr and lcurr in your program. I am a newbie in programming. But I am willing to know about it.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article