This procedure is somewhat more complex because it deals with three different possibilities, instead of just one. If the node pointed by value has no children, the conditions on lines 7, 8, and 9 are false, temp gets the value of T, and is deleted in line 13. In other words, if the node to be deleted has no children, we simply remove it.
If the node has only one child, either one of the two conditions in line 7 or 8 will be true, and the statements t=t->right or t=t->left will have the effect of "splicing out" the node by making a link between its child and its parent. After the link is made, the node is deleted in statement 13. The most complex situation arises when the node has two children. In this case, the procedure slices out the node's successor DELETE_MIN(T->right) and replaces the contents of T with the contents of the successor. This is represented in the code by the statements in lines 9-13. Notice that procedure DELETE_MIN, when passed the argument (T->right), finds and deletes the minimum value in the right subtree of T. Since this tree contains only contains values greater than T->value (and greater values cannot be anywhere else in the tree structure), finding its minimum corresponds to finding the successor of T.
DELETE (T, value)
NODE_PTR temp;
begin
1. if (T = NIL) then print("Value not in tree")
2. else if (value < T -> value) then DELETE (T->left, value)
3. else if (value > T -> value) then DELETE (T->right,value)
4. else begin /* After finding the node then delete it */
5. alloc_node(temp);
6. temp = T;
7. if (T->left = NIL) then T = T -> right
8. else if (T->right = NIL) then T = T -> left
9. else begin
10. temp = DELETE_MIN (T->right);
11. T -> value = temp -> value;
12. end else;
13. free_node(temp);
14 end else;
15.end begin.
Example 1:
Example 2: Example 3:
