import java.util.ArrayList;

/** BST implementation for Dictionary ADT */ class BST, E> implements Dictionary { private BSTNode root; // Root of BST private int nodecount; // Size of BST

/** Constructor */ BST() { root = null; nodecount = 0; }

/** Reinitialize tree */ public void clear() { root = null; nodecount = 0; }

/** * Insert a record into the tree. * * @param k * Key value of the record. * @param e * The record to insert. */ public void insert(K k, E e) { root = inserthelp(root, k, e); nodecount++; }

/** * Remove a record from the tree. * * @param k * Key value of record to remove. * @return Record removed, or null if there is none. */ public E remove(K k) { E temp = findhelp(root, k); // find it if (temp != null) { root = removehelp(root, k); // remove it // System.out.println("called removehelp"); nodecount--; } return temp; }

/** * Remove/return root node from dictionary. * * @return The record removed, null if empty. */ public E removeAny() { if (root == null) return null; E temp = root.element(); root = removehelp(root, root.key()); --nodecount; return temp; }

/** * @return Record with key k, null if none. * @param k * The key value to find. */ public E find(K k) { return findhelp(root, k); }

/** @return Number of records in dictionary. */ public int size() { return nodecount; }

private E findhelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) return findhelp(rt.left(), k); else if (rt.key().compareTo(k) == 0) return rt.element(); else return findhelp(rt.right(), k); }

private BSTNode inserthelp(BSTNode rt, K k, E e) { if (rt == null) return new BSTNode(k, e); if (rt.key().compareTo(k) > 0) rt.setLeft(inserthelp(rt.left(), k, e)); else rt.setRight(inserthelp(rt.right(), k, e)); return rt; }

private BSTNode getmin(BSTNode rt) { if (rt.left() == null) return rt; else return getmin(rt.left()); }

private BSTNode deletemin(BSTNode rt) { if (rt.left() == null) return rt.right();

else { rt.setLeft(deletemin(rt.left())); return rt; } }

/** * Remove a node with key value k * * @return The tree with the node removed */ private BSTNode removehelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) rt.setLeft(removehelp(rt.left(), k)); else if (rt.key().compareTo(k) temp = getmin(rt.right()); rt.setElement(temp.element()); rt.setKey(temp.key()); rt.setRight(deletemin(rt.right())); } } return rt; }

/** * Creates a list storing the the nodes in the subtree of a node, ordered * according to the inorder traversal of the subtree. */

protected void inorderElements(BSTNode v, ArrayList elts) { // elts.add(v.element()); if (v.left() != null) inorderElements(v.left(), elts); // recurse on left child elts.add(v.element()); if (v.right() != null) inorderElements(v.right(), elts); // recurse on right child }

/** Returns an iterable collection of the tree nodes. */ public Iterable values() { ArrayList elements = new ArrayList(); if (size() != 0) inorderElements(root, elements); // assign positions in order return elements; }

public Iterable findAll(K k) { ArrayList al = new ArrayList(); findAllhelp(root, k, al); return al; }

protected void findAllhelp(BSTNode rt, K k, ArrayList a) { if (rt == null) return; if (rt.key().compareTo(k) > 0) findAllhelp(rt.left(), k, a); else if (rt.key().compareTo(k) == 0) { a.add(rt.element()); findAllhelp(rt.right(), k, a); } else findAllhelp(rt.right(), k, a); }

/* the following are for solving the exercises in Shaffer, ch. 5 */

public Iterable range(K a, K b) { ArrayList elements = new ArrayList(); rangehelp(root, elements, a, b); return elements; }

protected void rangehelp(BSTNode v, ArrayList elts, K a, K b) { // fill in } }

The BSTDictionary class on moodle has a method range with the following declaration: public Iterable range(K a, K b) Passed a low key value a and a high key value b, range should return an ArrayList that contains all the dictionary values with key between a and b, inclusive, in order The range method relies on the rangehelp method, which is not fully implemented. Complete the definition of rangehelp. Use the program PrintRange.java to test your method. It reads in the shuffled cmu pronunciation dictionary and creates a dictionary keyed on word. The program reads two strings from the terminal, and prints out all records with keys that fall between the two given strings, inclusive. Your range method should visit as few nodes in the BST as possible. For example, with input DOFF DOG PrintRange should produce the output DOFF D A01 F DOFFING D A01 F IHO NG DOFFSD A01 F S DOG D A01 G The BSTDictionary class on moodle has a method range with the following declaration: public Iterable range(K a, K b) Passed a low key value a and a high key value b, range should return an ArrayList that contains all the dictionary values with key between a and b, inclusive, in order The range method relies on the rangehelp method, which is not fully implemented. Complete the definition of rangehelp. Use the program PrintRange.java to test your method. It reads in the shuffled cmu pronunciation dictionary and creates a dictionary keyed on word. The program reads two strings from the terminal, and prints out all records with keys that fall between the two given strings, inclusive. Your range method should visit as few nodes in the BST as possible. For example, with input DOFF DOG PrintRange should produce the output DOFF D A01 F DOFFING D A01 F IHO NG DOFFSD A01 F S DOG D A01 G