IC312: Data Structures (FA17)

Home Policy Calendar Units Assignments Resources

HW 5: BST Map [SOLUTION]

Solution

``````public class BST<K extends Comparable<K>,V> implements Map<K,V>{

private class Node{
Node left;
Node right;
K key;
V value;

public Node(K k, V v){
key=k;
value=v;
left=right=null;
}

}

private Node root;
private int numElem;

public BST(){
root=null;
numElem = 0;
}

public int size(){
return numElem;
}

public V get(K key){
return get(root,key);
}

private V get(Node n ,K key){
if(n == null) return null;

if(n.key.compareTo(key) == 0 )
return n.value;
else if(n.key.compareTo(key) > 0 )
return get(n.left,key);
else
return get(n.right,key);
}

public void set(K key, V value){
root = set(root, key, value);
}

private Node set(Node n, K key, V value){
if(n == null){
//new node, increase the size
numElem+=1;
return new Node(key,value);
}

if(n.key.compareTo(key) == 0 ){

//should we subtract or add to the size for a key that
//previously existed?
if(n.value != null && value == null)
numElem-=1;

if(n.value == null && value != null)
numElem+=1;

n.value=value;
return n;
} else if(n.key.compareTo(key) > 0 ){
n.left = set(n.left,key,value);

}else{
n.right = set(n.right,key,value);
}

return n;
}

public List<K> keys(){
ArrayList<K> list = new ArrayList<K>();
keys(root,list);
return list;
}

private void keys(Node n, ArrayList<K> l){
if( n== null) return;
keys(n.left, l);
if(n.value != null) //shouldn't include keys with null values!
l.push(n.key);
keys(n.right, l);
}

public List<V> values(){
ArrayList<V> list = new ArrayList<V>();
values(root,list);
return list;
}

private void values(Node n, ArrayList<V> l){
if( n== null) return;
values(n.left,l);
if(n.value != null) //shouldn't include values that are null!
l.push(n.value);
values(n.right,l);
}
``````