BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 946

4 return true ;

5
6 Let current be the node that contains e and parent be
7 the parent of current;
8
9 if (current has no left child) // Case 1
10 Connect the right child of
11 current with parent; now current is not referenced, so
12 it is eliminated;
13 else // Case 2
14 Locate the rightmost node in the left subtree of current.
15 Copy the element value in the rightmost node to current.
16 Connect the parent of the rightmost node to the left child
17 of rightmost node;
18
19

locate current
locate parent

Case 1

Case 2

return true ; // Element deleted

20 }

The complete implementation of the delete method is given in lines 155-213 in Listing
25.5. The method locates the node (named current ) to be deleted and also locates its parent
(named parent ) in lines 157-170. If current is null , the element is not in the tree. There-
fore, the method returns false (line 173). Please note that if current is root , parent is
null . If the tree is empty, both current and parent are null .
Case 1 of the algorithm is covered in lines 176-187. In this case, the current node has
no left child (i.e., current.left == null ). If parent is null , assign current.right
to root (lines 178-180). Otherwise, assign current.right to either parent.left or
parent.right , depending on whether current is a left or right child of parent (182-185).
Case 2 of the algorithm is covered in lines 188-209. In this case, current has a left child.
The algorithm locates the rightmost node (named rightMost ) in the left subtree of the cur-
rent node and also its parent (named parentOfRightMost ) (lines 195-198). Replace the
element in current by the element in rightMost (line 201); assign rightMost.left
to either parentOfRightMost.right or parentOfRightMost.left (lines 204-208),
depending on whether rightMost is a right or left child of parentOfRightMost .
Listing 25.8 gives a test program that deletes the elements from the binary search tree.

L ISTING 25.8

TestBSTDelete.java
1 public class TestBSTDelete {
2 public static void main(String[] args) {
3 BST<String> tree = new BST<>();
4 tree.insert( "George" );
5 tree.insert( "Michael" );
6 tree.insert( "Tom" );
7 tree.insert( "Adam" );
8 tree.insert( "Jones" );
9 tree.insert( "Peter" );
10 tree.insert( "Daniel" );
11 printTree(tree);
12
13 System.out.println( "\nAfter delete George:" );
14 tree.delete( "George" );
15 printTree(tree);
16
17 System.out.println( "\nAfter delete Adam:" );
18 tree.delete( "Adam" );
19 printTree(tree);
20
21 System.out.println( "\nAfter delete Michael:" );
22

delete an element

delete an element

tree.delete( "Michael" ); delete an element