Author : Unknown
Page : << Previous 2
prev->right = temp->right;
delete temp;
return;
}
if(temp->right == NULL && !left)
{
prev->right = temp->left;
delete temp;
return;
}
// the difficult case where both children are nonempty
while(temp->left != NULL && temp->right != NULL)
{
temp->data = temp->right->data;
prev = temp;
temp = temp->right;
}
if(temp->right == NULL)
prev->right = temp->left;
if(temp->left == NULL)
prev->right = temp->right;
delete temp;
return;
}
prev = temp;
if(temp->data temp = temp->right;
else temp = temp->left;
}
}
As I said the remove function is basically just a find with some extra tracking. It looks much more complex because of what happens when we find the item we're looking for. The code before and after this if statement is identical to the code in the find function.
The complexity in the remove function is caused by having two nodes to go to from each node. For linked lists all we had to do was assign prev->next to temp->next to bypass temp. In this case the previous node has one link that points to temp and the other that points to a different tree altogether. We must take this into account. In addition there are four possible cases for the pointers from temp. These are:
-both pointers are NULL; ie no children
-the left pointer is NULL, but the right has children
-the right pointer is NULL, but the left has children
-both pointers are not NULL; temp has children from both
The first three cases are fairly easy to deal with. There is one pointer to temp and one meaningful pointer from temp so we set the pointer to temp equal to the pointer from temp and bypass temp that way (if both the pointers from temp are NULL then it doesn't matter which we choose). These cases are dealt with in the first four if statements. In these statements left is 1 if temp to the left of the previous node and 0 otherwise.
The last case is the hardest to deal with. In this case there is a pointer to temp in the previous node, but two meaningful pointers from temp. A simple assignment will not do. The answer is to turn it into one of the easy cases. To do this we copy the data from temp's right node into temp and then we go right. We keep doing this until we get to a node with one or zero children. Think about what this did. The first assignment removed the data in temp, but it also created a duplicate node. We're now moving that duplicate down the tree until we get to the end where we can delete it as above.
Page : << Previous 2