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