I have most of the class done I just need help with the remove function and both
ID: 3547568 • Letter: I
Question
I have most of the class done I just need help with the remove function and both iterators. Remove deletes the key/value pair identified by the key parameter and returns true if the key/value pair was found and removed otherwise false. Key iterator returns an Iterator of the keys in the dictionary, in ascending sorted order. The iterator must be fail-fast. Value iterator returns an Iterator of the values in the dictionary. The order of the values must match the order of the keys. The iterator must be fail-fast.
package data_structures;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class BinarySearchTree<K,V> implements DictionaryADT<K,V> {
private Node<K,V> root;
private int currentSize;
class Node<K,V> { //creates Node and has nested constructor
private K key;
private V value;
private Node left, right;
public Node (K k, V v) {
key = k;
value = v;
left = right = null;
}
}
public boolean contains(K key) {
return getValue(key) != null;
}
public boolean insert(K key, V value) {
if (contains(key))
return false;
if (root == null)
root = new Node<K,V>(key,value);
else
add(key,value,root,null,false);
currentSize++;
return true;
}
private void add(K key,V value,Node<K,V> n,Node<K,V> parent, boolean wasLeft) {
if (n == null) {
if (wasLeft)
parent.left = new Node<K,V>(key,value);
else
parent.right = new Node<K,V>(key,value);
}
else if (((Comparable<K>)key).compareTo((K)n.key) < 0 )
add(key,value,n.left,n,true);
else
add(key,value,n.right,n,false);
}
public boolean remove(K key) {
}
public V getValue(K key) {
if (root == null)
return null;
Node<K,V> current = root;
while (((Comparable<K>)current.key).compareTo((K)key) != 0) {
if (((Comparable<K>)key).compareTo((K)current.key) < 0)
current = current.left;
else
current = current.right;
if (current == null)
return null;
}
return current.value;
}
public K getKey(V value) {
if (root == null)
return null;
Node<K,V> current = root;
while (((Comparable<V>)current.value).compareTo((V)value) != 0) {
if (((Comparable<V>)value).compareTo((V)current.value) < 0)
current = current.left;
else
current = current.right;
if (current == null)
return null;
}
return current.key;
}
public int size() {
return currentSize;
}
private int size(Node x) {
if (x == null)
return 0;
else
return currentSize;
}
public boolean isFull() {
return false;
}
public boolean isEmpty() {
return size() == 0;
}
public void clear() {
root = null;
}
public Iterator<K> keys() {
}
public Iterator<V> values() {
}
}
Explanation / Answer
public class BST<Key extends Comparable<Key>,Value>{
private Node root;
private class Node{
private 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;}
}
public int size(){
return size(root);
}
public int size(Node x){
if(x==null) return 0;
else
return x.N;
}
public Value get(Key key){
return get(root,key);
}
private Value get(Node x, Key key){
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;
}
public Node put(Key key,Value val){
root = put(root,Key,val);
}
private Node put(Node x, Key key, Value 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;
}
public Key min(){
return min(root).key;
}
private Node min(Node x){
if(x.left==null) return x;
return min(x.left);
}
public Key max(){
return min(root).key;
}
private Node max(Node x){
if(x.right==null) return x;
return max(x.right);
}
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(x.left,k);
else if(t<k) return(x.right,k-t-1);
else return x;
}
public int rank(Key key,Node x)
{ return rank(key,root); }
private int rank(Key key,Node 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);
}
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;
}
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;
}
}