package tesfaibstst; /** * Ordered symbol table interface. * * @author Sedgewick and Wayne, Acuna * @param search key * @param return type */ 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); }

package tesfaibstst; /** * Symbol table interface. * * @author Sedgewick and Wayne, Acuna * @param search key * @param return type */ 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(); }

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

Implementing a Binary Search Tree Summary: In this assignment, you will complete the implementation of a Binary Search Tree, and write veral methods that manipulate it 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. B are nice structures for searching, because they mimic the process of a binary search STs CO(logn)). Unfortunately, fast O(logn) look ups only work in BSTs that are balanced. Any time we remove or add nodes, there is a chance the tree will become stilted, which can degrade search t 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 xpected of you in this homework. In Testing, we give some basic suggestions on how the tree additions should be tested. Lastly, Submission discusses how your source code should be submitted on BlackBoard 2 Requirements 150 pointsl In this assignment you will practice implementing symbol tables using BST's. 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 0, isEmpty0, ceiling(), deleteMax0, and size 10 points Recursive methods are nice since it is easy to tell they work, however, they tend to be slo than non recursive methods. Give non-recursive implementations of get0 and put (Hint: the book contains the solution for one of these.) 15 pointsl 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. (Come up with a way yourself don't skip to 3.3.) 120 pointsl Sedgewick 3.2.37: Write a method print Level (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 elle. I15 points