Implement contains(), isEmpty(), ceiling(), deleteMax(), and size(Key lo, Key hi).

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 the solution for one of these.)

Write a method that balances an existing BST, call it balance(). If the tree is balanced, then searching for keys will take act like binary search and require only logn comparisons.

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 Queue.

/** * A binary search tree based implementation of a symbol table. * * @author (your name), Sedgewick and Wayne, Acuna * @version (version) */ 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.left, key); else 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.left = put(x.left, key, val); else 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 max(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 < 0) return floor(x.left, key); Node t = floor(x.right, key); if (t != null) return t; else return x; } @Override public Key select(int k) { return select(root, k).key; } private Node select(Node x, int k) { if (x == null) return null; int t = size(x.left); if (t > k) return select(x.left, k); else if (t < k) return select(x.right, k-t-1); else return x; } @Override public int rank(Key key) { return rank(key, root); } private int rank(Key key, Node x) { // Return number of keys less than x.key in the subtree rooted at x. if (x == null) return 0; int cmp = key.compareTo(x.key); if (cmp < 0) return rank(key, x.left); else if (cmp > 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.left = delete(x.left, key); else 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) keys(x.left, queue, lo, hi); if (cmplo <= 0 && cmphi >= 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 int 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 } }