avltree.java

真的很麻烦也

/** Realization of a dictionary by means of an AVL tree. */
public class AVLTree extends BinarySearchTree implements Dictionary  
{
  public AVLTree(Comparator c)  {
    super(c);
    T = (LinkedBinaryTree) new LinkedBinaryTree();
  }
  private int height(Position p)  {
    if(T.isExternal(p))
      return 0;
    else
      return ((AVLItem) p.element()).height();
  }
  private void setHeight(Position p)  { // called only if p is internal
    ((AVLItem) p.element()).setHeight(1+Math.max(height(T.leftChild(p)),
						 height(T.rightChild(p))));
  }
  private boolean isBalanced(Position p)  {
    // test whether node p has balance factor between -1 and 1
    int bf = height(T.leftChild(p)) - height(T.rightChild(p));
    return ((-1 <= bf) &&  (bf <= 1));
  }
  private Position tallerChild(Position p)  {
    // return a child of p with height no smaller than that of the other child
    if(height(T.leftChild(p)) >= height(T.rightChild(p)))
      return T.leftChild(p);
    else
      return T.rightChild(p);
  }
  /**  
    * Auxiliary method called by insertItem and removeElement.
    * Traverses the path of T from the given node to the root. For
    * each node zPos encountered, recomputes the height of zPos and
    * performs a trinode restructuring if zPos is unbalanced.
    */
  private void rebalance(Position zPos) {
    while (!T.isRoot(zPos)) {
      zPos = T.parent(zPos);
      setHeight(zPos);
      if (!isBalanced(zPos)) { 
	// perform a trinode restructuring
        Position xPos =  tallerChild(tallerChild(zPos));
        zPos = ((LinkedBinaryTree) T).restructure(xPos);
        setHeight(T.leftChild(zPos));
        setHeight(T.rightChild(zPos));
        setHeight(zPos);
      }
    }
  }

  // methods of the dictionary ADT

  /** Overrides the corresponding method of the parent class. */
  public void insertItem(Object key, Object element)
      throws InvalidKeyException  {
    super.insertItem(key, element); // may throw an InvalidKeyException
    Position zPos = actionPos; // start at the insertion position
    T.replaceElement(zPos, new AVLItem(key, element, 1));
    rebalance(zPos);
  }

  /** Overrides the corresponding method of the parent class. */
  public Object removeElement(Object key)
      throws InvalidKeyException {
    Object toReturn = super.removeElement(key);
    				// may throw an InvalidKeyException
    if(toReturn != NO_SUCH_KEY) {
      Position zPos = actionPos; // start at the removal position
      rebalance(zPos);
    }
    return toReturn;
  }
}