Please help with this Java Program In this assignment you will practice implemen
ID: 3745626 • Letter: P
Question
Please help with this Java Program
In this assignment you will practice implementing symbol tables using BSTs. Download the attached base le and then rename it, and the class inside, to include your last name instead of "Base". You will only need to change the base le. The purpose of OrderedSymbolTable and SymbolTable are only to de ne the ADTs which the BST data structure supports.
• Implement contains(), isEmpty(), ceiling(), deleteMax(), and size(Key lo, Key hi). [5 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 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. (Come up with a way yourself
• 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.
The base file is below for reference.
Explanation / Answer
The answer below contains the solution for only first subpart.
Program:
**
* 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 SinghaniaBSTST<Key extends Comparable<Key>, Value> implements OrderedSymbolTable<Key, Value> {
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 key’s 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<Key> keys() {
return keys(min(), max());
}
@Override
public Iterable<Key> keys(Key lo, Key hi)
{
Queue<Key> queue = new LinkedList<>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> 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) {
if (key == null)
return null;
return get(key) != null;
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public Key ceiling(Key key) {
if (key == null)
return null;
if (isEmpty()) throw new NoSuchElementException("symbol table is empty");
Node x = ceiling(root, key);
if (x == null) return null;
else return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) return null;
int compare = key.compareTo(x.key);
if (compare == 0) return x;
if (compare < 0) {
Node tree = ceiling(tree.left, key);
if (tree != null) return tree;
else return x;
}
return ceiling(x.right, key);
}
@Override
public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
root = deleteMax(root);
assert check();
}
private Node deleteMax(Node deleted) {
if (deleted.right == null) return deleted.left;
deleted.right = deleteMax(deleted.right);
deleted.size = size(deleted.left) + size(deleted.right) + 1;
return deleted;
}
@Override
public int size(Key lo, Key hi) {
if (lo.compareTo(hi) > 0)
return 0;
if (contains(hi))
return rank(hi) - rank(lo) + 1;
else
return rank(hi) - rank(lo);
}
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) {
SinghaniaBSTST<Integer, String> bst = new SinghaniaBSTST();
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
}
}