binarysearchtree.java

真的很麻烦也

/** Realization of a dictionary by means of a binary search tree */
public class BinarySearchTree implements Dictionary  {
  Comparator C;  // comparator
  LinkedBinaryTree T; // binary tree
  final Object NO_SUCH_KEY = null;
  protected Position actionPos; // insertion position or parent of removed position

  public BinarySearchTree(Comparator c)  {
    C = c;
    T = (LinkedBinaryTree) new LinkedBinaryTree();
  }
  
  // auxiliary methods:
  /** Extract the key of the item at a given node of the tree. */
  protected Object key(Position position)  {
    return ((Item) position.element()).key();
  }
  /** Extract the element of the item at a given node of the tree. */  
  protected Object element(Position position)  { 
    return ((Item) position.element()).element(); 
  }
  /** Check whether a given key is valid. */  
  protected void checkKey(Object key) throws InvalidKeyException {
    if(!C.isComparable(key))
      throw new InvalidKeyException("Key "+key+" is not comparable");
  }
  /** Auxiliary method used by removeElement. */
  protected void swap(Position swapPos, Position remPos){
    T.replaceElement(swapPos, remPos.element());
  }
  /** Auxiliary method used by findElement, insertItem, and removeElement. */
  protected Position findPosition(Object key, Position pos) {
    if (T.isExternal(pos))
      return pos; // key not found and external node reached returned
    else {
      Object curKey = key(pos);
      if(C.isLessThan(key, curKey))
        return findPosition(key, T.leftChild(pos));
      else if(C.isGreaterThan(key, curKey)) // search in left subtree
        return findPosition(key, T.rightChild(pos)); // search in right subtree
      else
        return pos; // return internal node where key is found
    }
  }

  // methods of the dictionary ADT
  public int size()  { 
    return (T.size() - 1) / 2; 
  }
  
  public boolean isEmpty() { 
    return T.size() == 1;
  }
  
  public Object findElement(Object key) throws InvalidKeyException {
    checkKey(key); // may throw an InvalidKeyException
    Position curPos = findPosition(key, T.root());
    actionPos = curPos; // node where the search ended
    if (T.isInternal(curPos))
      return element(curPos);
    else
      return NO_SUCH_KEY;
  }
  public void insertItem(Object key, Object element)
    throws InvalidKeyException  {
    checkKey(key); // may throw an InvalidKeyException
    Position insPos = T.root();
    do {
      insPos = findPosition(key, insPos);
      if (T.isExternal(insPos))
        break;
      else // the key already exists
      {
	      Object elem = (((Item)(insPos.element())).element());     
	      int wordNum = ((Integer)elem).intValue();
	      wordNum+=1;
	      ((Item)(insPos.element())).setElement(new Integer(wordNum));
	      return;
      }
        //insPos = T.rightChild(insPos);
    } while (true);
    T.expandExternal(insPos);
    Item newItem = new Item(key, element);
    T.replaceElement(insPos, newItem);
    actionPos = insPos; // node where the new item was inserted
  }
  
  public Object removeElement(Object key) throws InvalidKeyException  {
    Object toReturn;
    checkKey(key); // may throw an InvalidKeyException
    Position remPos = findPosition(key, T.root());
    if(T.isExternal(remPos)) {
      actionPos = remPos; // node where the search ended unsuccessfully
      return NO_SUCH_KEY;
    }
    else{
      toReturn = element(remPos); // element to be returned
      if (T.isExternal(T.leftChild(remPos)))
        remPos = T.leftChild(remPos);
      else if (T.isExternal(T.rightChild(remPos)))
        remPos = T.rightChild(remPos);
      else { // key is at a node with internal children
        Position swapPos = remPos; // find node for swapping items
        remPos = T.rightChild(swapPos);
        do
	  remPos = T.leftChild(remPos);
	while (T.isInternal(remPos));
	swap(swapPos, T.parent(remPos));
      }
      actionPos = T.sibling(remPos); // sibling of the leaf to be removed
      T.removeAboveExternal(remPos);
      return toReturn;
    }
  }
}