/**  
    * 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 = ((RestructurableNodeBinaryTree) 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;
  }