SymbolTable.java$-$

package edu.ser$222.$m$03\_02$;

$/**$

$*$ Symbol table interface.

$*$

$*$ @author Sedgewick, 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. returns null if key does not exist.

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$()$;

$//$number of key$-$value pairs

int size$()$;

$//$all keys in the table

Iterable keys$()$;

$\}$

OrderedSymbolTable.java$-$

package edu.ser$222.$m$03\_02$;

$/**$

$*$ Ordered symbol table interface.

$*$

$*$ @author Sedgewick, Acuna

$*$ @param search key

$*$ @param return type

$*/$

public interface OrderedSymbolTable extends SymbolTable $\{$

$/**$

$*$ Returns the minimum key.

$*$ @throws NoSuchElementException if the ST is empty

$*$ @return minimum key.

$*/$

Key min$()$;

$/**$

$*$ Returns the maximum key.

$*$ @throws NoSuchElementException if the ST is empty

$*$ @return maximum key.

$*/$

Key max$()$;

$/**$

$*$ Returns largest key less than or equal to key. If no such key exists,

returns null.

$*$ @throws NoSuchElementException if the ST is empty

$*$ @param key target floor

$*$ @return closest key

$*/$

Key floor$($Key key$)$;

$/**$

$*$ Returns smallest key greater than or equal to key. If no such key exists,

returns null.

$*$ @throws NoSuchElementException if the ST is empty

$*$ @param key target floor

$*$ @return closest key

$*/$

Key ceiling$($Key key$)$;

$/**$

$*$ Returns number of keys less than key.

$*$ @param key target key

$*$ @return rank

$*/$

int rank$($Key key$)$;

$/**$

$*$ Returns key of rank k$.$

$*$ @param k target rank

$*$ @return key

$*/$

Key select$($int k$)$;

$/**$

$*$ Delete smallest key.

$*$ @throws NoSuchElementException if the ST is empty

$*/$

void deleteMin$()$;

$/**$

$*$ Deletes largest key.

$*$ @throws NoSuchElementException if the ST is empty

$*/$

void deleteMax$()$;

$/**$

$*$ Returns the number of keys in $[$lo$..$hi$].$

$*$ @param lo begining of range

$*$ @param hi end of range

$*$ @return number of keys

$*/$

int size$($Key lo$,$ Key hi$)$;

$/**$

$*$ Returns all keys in $[$lo$..$hi$]$ in sorted order.

$*$ @param lo begining of range

$*$ @param hi end of range

$*$ @return Iterable container of keys.

$*/$

Iterable keys$($Key lo$,$ Key hi$)$;

$\}$

BST$.$java$-$

package edu.ser$222.$m$03\_02$;

$/**$

$*$ BST defines an interface to a BST implementation of OrderedSymbolTable that

offers methods

$*$ specific to trees.

$*$

$*$ @author Acuna

$*$ @version $1\mathrm{.}0$

$*$ @param contained key type

$*$ @param contained value type

$*/$

public interface BST extends OrderedSymbolTable$\{$

$/**$

$*$ Puts a key value pair into the tree. If key already exists, then only

updates value.

$*$ @param key key to add

$*$ @param val value for key

$*/$

void putFast$($Key key, Value val$)$;

$/**$

$*$ Returns the value paired with a key in the tree. Returns null if key does

not exist.

$*$ @param key key to find

$*$ @return value of key

$*/$

Value getFast$($Key key$)$;

$/**$

$*$ Returns a string representation of the tree. The ordering is a level

traversal of the tree,

$*$ and each node's value is separated by a space. If there is no valid subtree

rooted at the

$*$ given key, returns "empty".

$*$ @return the level order string representation of the tree

$*/$

public String displayLevel$($Key key$)$;

public void balance$()$;

$/**$

$*$ Returns the root node of the BST$.$

$*$ @return the root node

$*/$

public Node getRoot$()$;

$\}$

Node.java$-$

package edu.ser$222.$m$03\_02$;

$/**$

$*$ A class to represent a node in a binary search tree.

$*$

$*$ @author Sedgewick, Acuna

$*$ @version $1\mathrm{.}0$

$*$ @param contained key type

$*$ @param contained value type

$*/$

public class Node $\{$

public final Key key;

public Value val;

public Node left, right;

public int N;

public Node$($Key key, Value val, int N$)\{$

this.key $=$ key; this.val $=$ val; this.N $=$ N;

$\}$

$\}$

CompletedBST.java$-$

package edu.ser$222.$m$03\_02$;

$/**$

$*$ A binary search tree based implementation of a symbol table.

$*$

$*$ Completion time: $($your completion time$)$

$*$

$*$ @author $($your name$),$ Sedgewick, Acuna

$*$ @version $($version$)$

$*/$

import java.util.Collections;

import java.util.LinkedList;

import java.util.NoSuchElementException;

import java.util.Queue;

public class CompletedBST, Value$>$ implements BST $\{$

private Node root;

@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$)\{$

Node iter $=$ root;

while$($iter $!=$ null$)\{$

int cmp $=$ key.compareTo$($iter$.$key$)$;

if $($cmp $<mtext\; id="EditorElement\_9431318"></mtext><mn\; id="EditorElement\_9431319">0</mn><mi\; id="EditorElement\_9431320">)</mi>$

iter $=$ iter.left;

else if $($cmp $>0)$

iter $=$ iter.right;

else

return iter.val;

$\}$

return null;

$\}$

private Value get$($Node x$,$ Key key$)$

$\{$

etc the whole compltedbst.java is not fitting here help!!