Source of 25.30.java


  1: // Removes an entry from the tree rooted at a given node.
  2: // rootNode is a reference to the root of a tree.
  3: // entry is the object to be removed.
  4: // oldEntry is an object whose data field is null.
  5: // Returns the root node of the resulting tree; if entry matches
  6: //         an entry in the tree, oldEntry's data field is the entry
  7: //         that was removed from the tree; otherwise it is null.
  8: private BinaryNode<T> removeEntry(BinaryNode<T> rootNode, T entry,
  9:                                   ReturnObject oldEntry)
 10: {
 11:    if (rootNode != null)
 12:    {
 13:       T rootData = rootNode.getData();
 14:       int comparison = entry.compareTo(rootData);
 15: 
 16:       if (comparison == 0)       // entry == root entry
 17:       {
 18:          oldEntry.set(rootData);
 19:          rootNode = removeFromRoot(rootNode);
 20:       }
 21:       else if (comparison < 0)   // entry < root entry
 22:       {
 23:          BinaryNode<T> leftChild = rootNode.getLeftChild();
 24:          BinaryNode<T> subtreeRoot = removeEntry(leftChild, entry, oldEntry);
 25:          rootNode.setLeftChild(subtreeRoot);
 26:       }
 27:       else                       // entry > root entry
 28:       {
 29:          BinaryNode<T> rightChild = rootNode.getRightChild();
 30:          rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry));
 31:       } // end if
 32:    } // end if
 33: 
 34:    return rootNode;
 35: } // end removeEntry
 36: // Version 4.0