/** 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 }