// Realization of a dictionary by means of a binary search tree
public class BinarySearchTree extends LinkedBinaryTree implements Dictionary {
  // Instance variables:
  protected Comparator C;	// comparator
  protected Position actionPos;	// insertion node or parent of removed node
  protected int numEntries = 0;	// number of entries
  /** Creates a BinarySearchTree with a default comparator. */
  public BinarySearchTree()  { 
    C = new DefaultComparator(); 
    addRoot(null);
  }
  public BinarySearchTree(Comparator c)  { 
    C = c; 
    addRoot(null);
  }
  /** Nested class for location-aware binary search tree entries */
  protected static class BSTEntry implements Entry {
    protected Object key;
    protected Object value;
    protected Position pos;
    BSTEntry() { /* default constructor */ }
    BSTEntry(Object k, Object v, Position p) { key = k; value = v; pos = p;}
    public Object key() { return key; }
    public Object value() { return value; }
    public Position position() { return pos; }
  }
  // Auxiliary methods:
  /** Extract the key of the entry at a given node of the tree. */
  protected Object key(Position position)  {
    return ((Entry) position.element()).key();
  }
  /** Extract the value of the entry at a given node of the tree. */  
  protected Object value(Position position)  { 
    return ((Entry) position.element()).value(); 
  }
  /** Extract the entry at a given node of the tree. */  
  protected Entry entry(Position position)  { 
    return (Entry) position.element();
  }
  /** Replace an entry with a new entry (and reset the entry's location) */
  protected void replaceEntry(Position pos, Entry ent) {
    ((BSTEntry) ent).pos = pos;
    replace(pos, ent);
  }