dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: Delete node from BST - iterative

  1. #1
    Join Date
    Jan 2012
    Posts
    54

    Delete node from BST - iterative

    Hello
    I have write program in c++ which delete node from BST. It work for some level.Mean it wrok well when some nodes are delte but when i delete root node program print garbage value infinite time... Here is my code
    Code:
    void del(int num)
    {
    	struct list *current,*pre,*target;
    	current=root;
    	if(current==NULL)
    		return;
    	while((current->left !=NULL) && (current->right!=NULL))
    	{
    		if(current->data==num)
    			target=current;
    		if(num < current->data)
    		{
    			if(current->left ==NULL)
    				break;
    			pre=current;
    			current=current->left;
    		}
    		else
    		{
    			if(current->right==NULL)
    				break;
    			pre=current;
    			current=current->right;
    		}
    	}
    	if(target == NULL)
    		return;
    	else
    	{
    		if(pre==NULL)
    		{
    			free(current);
    			root=NULL;
    		}
    		else
    		{
    			target->data=current->data;
    			if(pre->left==current)
    				pre->left=current->right;
    			else
    				pre->right=current->left;
    			free (current);
    		}
    	}
    }
    anyone help me! and also tell how can i find leaf node in BST....any idea or algorithm?

  2. #2
    Join Date
    Jan 2012
    Posts
    54

    Delete node from BST - iterative

    anyone help me? plzz

  3. #3
    Join Date
    Jan 2009
    Posts
    596

    Re: Delete node from BST - iterative

    Have you tried using the debugger? This is an essential skill, unless of course you are one of those people who can write perfect code first time, every time. And there are very few of us around

    The first thing to do would be check the del function works on a tree which consists solely of the root node. It is quite clear that your code will not work in this case as it accesses an uninitialized pointer.

    Here is your code, with irrelevant bits deleted:
    Code:
    void del(int num)
    {
    	struct list *current,*pre,*target;
    	current=root;
    	if(current==NULL)
    		return;
    	while((current->left !=NULL) && (current->right!=NULL))
    	{
    		// while loop contents deleted...
    	}
    	if(target == NULL)
    		return;
    	else
    	{
    		// code deleted...
    	}
    }
    If there is only one node, then current->left and current->right will both be NULL (assuming they have been initialized correctly). This means the while loop will not run, and target (and also pre) will remain uninitialized when it is checked against NULL. And derefencing a junk pointer (later in the code) means only one thing can happen - which is that anything can happen.

  4. #4
    Join Date
    Jan 2012
    Posts
    54

    Re: Delete node from BST - iterative

    thanks for ans
    my program not work in only some case...For example
    Input data is 50,25,20,40,75,60,80 BST is created with inputted data
    Now first time i delete node 75 then it display ans 50 25 20 40 80 60
    Second time i delete node 20 then it display ans 50 25 40 80 60
    third time i delete node 25 then ans is 50 40 80 60
    fourth time i delete node root node 50 then ans 80 40 60
    fifth time i delete node 80 then ans is 40 60
    and last i delete node 40 at that time program display unknown symbol and also goes infinite....

    Program delete root at all other case but when there are fewer node at that time problem is created.
    Help me i try to do this program from several days....

  5. #5
    Join Date
    Jan 2009
    Posts
    596

    Re: Delete node from BST - iterative

    Quote Originally Posted by CSharpque View Post
    fifth time i delete node 80 then ans is 40 60
    and last i delete node 40 at that time program display unknown symbol and also goes infinite....
    When you only have two nodes, what do you think will happen when you get to this line:
    Code:
    	while((current->left !=NULL) && (current->right!=NULL))
    Hint: it's what I said in my previous post...

    Again, have you tried the debugger?

  6. #6
    Join Date
    Jan 2012
    Posts
    54

    Re: Delete node from BST - iterative

    yes i have use debugger...i have put if condition after completing while loop...
    Code:
    if(target == NULL)
    	{
    		if(root->left->data ==num)
    			target=root->left;
    
    		else if(root->right->data==num)
    			target=root->right;
    		else
    			return;
    	}
    but still program goes infinite....

  7. #7
    Join Date
    Jan 2009
    Posts
    596

    Re: Delete node from BST - iterative

    Quote Originally Posted by CSharpque View Post
    yes i have use debugger...i have put if condition after completing while loop...
    Code:
    if(target == NULL)
    	{
    		if(root->left->data ==num)
    			target=root->left;
    
    		else if(root->right->data==num)
    			target=root->right;
    		else
    			return;
    	}
    but still program goes infinite....
    That's because you still are not initializing target!
    target is only given a value in the while loop. This while loop will only run if current has both a left child and a right child.

  8. #8
    Join Date
    Jan 2012
    Posts
    54

    Re: Delete node from BST - iterative

    you are write i have declare target=NULL and also when node have only one child left or right at that time while loop condition become false... but i don't have any idea..can you suggest algorithm from that i can implement program...I am trying to implement this program from last 2 week but can't success..

  9. #9
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Delete node from BST - iterative

    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  10. #10
    Join Date
    Jan 2009
    Posts
    596

    Re: Delete node from BST - iterative

    Whenever you are having trouble with code, it is quite often because you are thinking about too much of the problem at a time. I would advise splitting the del function into two parts - one which finds the node corresponding to num and the other which deletes a node. E.g.:
    Code:
    void del(int num)
    {
    	list* node = findNode(num);
    	removeNode(node);
    }
    Here, findNode() returns NULL if num isn't found, and removeNode() does nothing if called with NULL.

    You will likely find a need for these functions elsewhere in the class also - so can reduce code duplication.

  11. #11
    Join Date
    Jun 2019
    Posts
    1

    Re: Delete node from BST - iterative

    This BST remove() function code (with iteration) works for all possible values I tested.
    Code:
    bool BST::remove(int x){
    		node *curr, *parent;
    		curr=root;
    		parent=NULL;
    		while(curr->data != x){
    			parent=curr;
    			if(x < curr->data)
    				curr=curr->left;
    			else if(x > curr->data)
    				curr=curr->right;
    			if(curr == NULL)
    				return false;                              /* value not found in binary search tree */
    		}
    		if(curr->left && curr->right){			/* Node having two child */ /* may be root node or not */
    			node *prev = curr;
    			node* child = curr->right;
    			while(child->left != NULL){
    				prev = child;
    				child=child->left;
    			}
    			curr->data = child->data;
    			if(child->right != NULL)
    				if(prev != curr)
    					prev->left = child->right;
    				else
    					prev->right = child->right;
    			else 
    				if(prev != curr)
    					prev->left = NULL;
    				else
    					prev->right = NULL;
    			delete child;
    		}
    		else if(parent != NULL){			/* When Node is not root node */
    			bool left=false;
    			if(x < parent->data)
    				left=true;
    			if(curr->left == NULL && curr->right == NULL){	// leaf node //
    				if(left==true)
    					parent->left=NULL;
    				else
    					parent->right=NULL;
    			}
    			else if(curr->right == NULL){					// one child //
    			if(left==true)
    				parent->left=curr->left;
    			else
    				parent->right = curr->left;
    		}
    		else if(curr->left == NULL){						// one child //
    			if(left==true)
    				parent->left=curr->right;
    			else
    				parent->right = curr->right;
    		}
    			delete curr;
    		}
    		else if(parent == NULL){							/* Root Node having single or no child */
    			if(curr->left == NULL && curr->right == NULL)
    				root = NULL;
    			else if(curr->left == NULL)
    				root = curr->right;
    			else if(curr->right == NULL)
    				root = curr->left;
    		}
    	}
    BST2.cppBST2.cpp

  12. #12
    Join Date
    Feb 2017
    Posts
    458

    Re: Delete node from BST - iterative

    For an extensive discussion I recommend Advanced Data Structures by Peter Brass. For some reason it's available on the net for free,

    https://doc.lagout.org/Others/Data%2...8-09-08%5D.pdf

    Search trees are presented in chapters 2 and 3. My main insight after reading was: Never ever even think of implementing a search tree yourself for use in production code . Fortunately this isn't necessary. The standard libraries of most languages today supply implementations.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)