/** Check whether a given key is valid. */  
  protected void checkKey(Object key) throws InvalidKeyException {
    if(key == null)  // just a simple test for now
      throw new InvalidKeyException("null key");
  }
  /** Check whether a given entry is valid. */
  protected void checkEntry(Entry ent) throws InvalidEntryException {
    if(ent == null || !(ent instanceof BSTEntry))
      throw new InvalidEntryException("invalid entry");
  }
  /** Auxiliary method for inserting an entry at an external node */
  protected Entry insertAtExternal(Position v, Entry e) {
    expandExternal(v,null,null);
    replace(v, e);
    numEntries++;
    return e;
  }
  /** Auxiliary method for removing an external node and its parent */
  protected void removeExternal(Position v) {
    removeAboveExternal(v);
    numEntries--;
  }
  /** Auxiliary method used by find, insert, and remove. */
  protected Position treeSearch(Object key, Position pos) {
    if (isExternal(pos)) return pos; // key not found; return external node
    else {
      Object curKey = key(pos);
      int comp = C.compare(key, curKey);
      if (comp < 0) 
	return treeSearch(key, left(pos));	// search left subtree
      else if (comp > 0)
	return treeSearch(key, right(pos));	// search right subtree
      return pos;		// return internal node where key is found
    }
  }
  // Adds to L all entries in the subtree rooted at v having keys equal to k
  protected void addAll(List L, Position v, Object k) {
    if (isExternal(v)) return;
    Position pos = treeSearch(k, v);
    if (!isExternal(pos))  {  // we found an entry with key equal to k 
      addAll(L, left(pos), k);
      L.insertLast(pos.element()); 	// add entries in inorder
      addAll(L, right(pos), k);
    } // this recursive algorithm is simple, but it's not the fastest
  }