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