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
        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;
    }
  }
}