1: public T remove(T entry)
2: {
3: T result = null;
4:
5: // Locate node (and its parent) that contains a match for entry
6: NodePair pair = findNode(entry);
7: BinaryNode<T> currentNode = pair.getFirst();
8: BinaryNode<T> parentNode = pair.getSecond();
9:
10: if (currentNode != null) // Entry is found
11: {
12: result = currentNode.getData(); // Get entry to be removed
13:
14: // Case 1: currentNode has two children
15: if (currentNode.hasLeftChild() && currentNode.hasRightChild())
16: {
17: // Replace entry in currentNode with the entry in another node
18: // that has at most one child; that node can be deleted
19:
20: // Get node to remove (contains inorder predecessor; has at
21: // most one child) and its parent
22: pair = getNodeToRemove(currentNode);
23: BinaryNode<T> nodeToRemove = pair.getFirst();
24: parentNode = pair.getSecond();
25:
26: // Copy entry from nodeToRemove to currentNode
27: currentNode.setData(nodeToRemove.getData());
28:
29: currentNode = nodeToRemove;
30: // Assertion: currentNode is the node to be removed; it has at
31: // most one child
32: // Assertion: Case 1 has been transformed to Case 2
33: } // end if
34:
35: // Case 2: currentNode has at most one child; delete it
36: removeNode(currentNode, parentNode);
37: } // end if
38:
39: return result;
40: } // end remove
41: // Version 4.0
42: