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