/** Realization of a dictionary by means of an AVL tree. */
public class AVLTree extends BinarySearchTree implements Dictionary  {
  public AVLTree(Comparator c)  {
    super(c);
    T = new RestructurableNodeBinaryTree();
  }
  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);
  }