import java.util.Collections; import java.util.LinkedList; import java.util.Queue; public class BaseBSTST, Value> implements OrderedSymbolTable { private Node root;

private class Node { private final Key key; private Value val; private Node left, right; private int N;

public Node(Key key, Value val, int N) { this.key = key; this.val = val; this.N = N; } } @Override public int size() { return size(root); } private int size(Node x) { if (x == null) return 0; else return x.N; } @Override public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { // Return value associated with key in the subtree rooted at x; // return null if key not present in subtree rooted at x. if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp 0) return get(x.right, key); else return x.val; } @Override public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { // Change keys value to val if key in subtree rooted at x. // Otherwise, add new node to subtree associating key with val. if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp 0) x.right = put(x.right, key, val); else x.val = val; x.N = size(x.left) + size(x.right) + 1; return x; } @Override public Key min() { return min(root).key; } private Node min(Node x) { if (x.left == null) return x; return min(x.left); } @Override public Key max() { return max(root).key; } private Node max(Node x) { if (x.right == null) return x; return min(x.right); } @Override public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; return x.key; } private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp k) return select(x.left, k); else if (t 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } @Override public void deleteMin() { root = deleteMin(root); } private Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; } @Override public void delete(Key key) { root = delete(root, key); } private Node delete(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp 0) x.right = delete(x.right, key); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; }

@Override public Iterable keys() { return keys(min(), max()); } @Override public Iterable keys(Key lo, Key hi) { Queue queue = new LinkedList(); keys(root, queue, lo, hi); return queue; } private void keys(Node x, Queue queue, Key lo, Key hi) { if (x == null) return; int cmplo = lo.compareTo(x.key); int cmphi = hi.compareTo(x.key); if (cmplo = 0) queue.add(x.key); if (cmphi > 0) keys(x.right, queue, lo, hi); } @Override public boolean contains(Key key) { throw new UnsupportedOperationException("Not supported yet."); }

@Override public boolean isEmpty() { throw new UnsupportedOperationException("Not supported yet."); }

@Override public Key ceiling(Key key) { throw new UnsupportedOperationException("Not supported yet."); } @Override public void deleteMax() { throw new UnsupportedOperationException("Not supported yet."); }

@Override public void size(Key lo, Key hi) { throw new UnsupportedOperationException("Not supported yet."); } public void balance() { throw new UnsupportedOperationException("Not supported yet."); } public void printLevel(Key key) { throw new UnsupportedOperationException("Not supported yet."); }

/** * entry point for testing. * * @param args the command line arguments */ public static void main(String[] args) { BaseBSTST bst = new BaseBSTST(); bst.put(10, "TEN"); bst.put(3, "THREE"); bst.put(1, "ONE"); bst.put(5, "FIVE"); bst.put(2, "TWO"); bst.put(7, "SEVEN"); System.out.println("Before balance:"); bst.printLevel(10); //root System.out.println("After balance:"); bst.balance(); bst.printLevel(5); //root } }

public interface SymbolTable { // put key-value pair into the table void put(Key key, Value val); //get value paired with key Value get(Key key); //remove key (and its value) from table void delete(Key key); //is there a value paired with key? boolean contains(Key key); //is the table empty? boolean isEmpty(); /umber of key-value pairs int size(); //all keys in the table, in sorted order Iterable keys(); }

public interface OrderedSymbolTable extends SymbolTable { //smallest key Key min(); //largest key Key max(); //largest key less than or equal to key Key floor(Key key); //smallest key greated than or equal to key Key ceiling(Key key); /umber of keys less than key int rank(Key key); //key of rank k Key select(int k); //delete smallest key void deleteMin(); //delete largest key void deleteMax(); /umber of keys in [lo..hi] int size(Key lo, Key hi); //keys in [lo..hi] in sorted order Iterable keys(Key lo, Key hi); }

1 Background In order to practice implementing symbol tables, you will implement a binary search tree. A BST can actually be considered to be another type of data structure that we can use to implement an ADT. Since symbol tables are about finding values based on keys (the "search" problem), it's appropriate to use a BST to implement them. BSTs are nice structures for searching, because they mimic the process of a binary search O(logra)). Unfortunately, fast O(logn) look ups only work in BST's that are balanced. Any time we remove or add nodes, there is a chance the tree will become stilted, which can degrade search to look like O(n) After we finish the implementation of a BST, we will go on to address this problem This document is separated into four sections Background Requirements, Testing, and Submission You have almost finished reading the Background section already. In Requirements, we will discuss what is expected of you in this homework. In Testing, we give some basic suggestions on how the tree addition hould be tested. Lastly, Submission discusses how your source code should be submitted on BlackBoard 2 Requirements [50 points In this assignment you will practice implementing symbol tables using BSTs. Download the attached base file and then rename it, and the class inside, to include your last name instead of "Base". You will only need to change the base file. The purpose of OrderedSymbolTable and SymbolTable are only to define the ADT which the BST data structure supports Implement contains isEmpty() ceiling deleteMax0, and size(). [10 points Recursive methods are nice since it is easy to tell they work, however, they tend to be slower than non recursive methods. Give non-recursive implementations of get and put (Hint: the book contains 15 points] the solution for one of these Write a method that balances an existing BST, call it balance 0. If the tree is balanced, then searching for keys will take act like binary search and require only logn comparisons. (Come up with a way yourself don't skip to 3.3.) 120 points] Sedgewick 3.2.37: Write a method printLevel(Key key) that takes a Key as argument and prints the keys in the subtree rooted at that node in level order (in order of their distance from the root, with nodes on each level in order from left to right). Hint: Use a ueue. [15 points] 3 Testing For most of the methods that you write, you should be able to tell if they are correct. However, the balance and print Level methods are more tricky. In the base file, there is sample code that builds a BST, displays it (using printLevel), balances it, and displays it again. The output is shown below. You may want to start by implementing printLevel and seeing if the output matches the screen shot for the "before balance state of the tree. Ideally you would write a couple of additional tests to verify that level-wise display is working