Source of 26.36.java


  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