/** Realization of a dictionary by means of a binary search tree */
public class BinarySearchTree implements Dictionary  {
  Comparator C;  // comparator
  BinaryTree T; // binary tree
  protected Position actionPos; // insertion position or parent of removed position

  public BinarySearchTree(Comparator c)  {
    C = c;
    T = (BinaryTree) new NodeBinaryTree();
  }
  
  // auxiliary methods:
  /** Extract the key of the item at a given node of the tree. */
  protected Object key(Position position)  {
    return ((Item) position.element()).key();
  }
  /** Extract the element of the item at a given node of the tree. */  
  protected Object element(Position position)  { 
    return ((Item) position.element()).element(); 
  }
  /** Check whether a given key is valid. */  
  protected void checkKey(Object key) throws InvalidKeyException {
    if(!C.isComparable(key))
      throw new InvalidKeyException("Key "+key+" is not comparable");
  }