-
April 12th, 2012, 04:36 AM
#1
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?
-
April 16th, 2012, 04:24 AM
#2
Delete node from BST - iterative
-
April 16th, 2012, 07:06 AM
#3
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.
-
April 18th, 2012, 12:11 AM
#4
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....
-
April 18th, 2012, 05:00 AM
#5
Re: Delete node from BST - iterative
Originally Posted by CSharpque
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?
-
April 19th, 2012, 11:29 AM
#6
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....
-
April 19th, 2012, 12:36 PM
#7
Re: Delete node from BST - iterative
Originally Posted by CSharpque
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.
-
April 20th, 2012, 10:26 AM
#8
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..
-
April 20th, 2012, 08:05 PM
#9
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.
-
April 21st, 2012, 05:11 AM
#10
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.
-
June 9th, 2019, 02:33 PM
#11
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
-
June 16th, 2019, 03:36 AM
#12
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|