Java

Please answer the highlighted

Big-O Analysis:

For each of the public methods of MyTreeMap, provide a Big-O analysis of the algorithm as you implemented it. For this analysis, assume that the current state of the tree is relatively balanced, that is the tree is close to minimal height. In other words, the tree is "bushy", rather than "spindly". Create a text document with the Big-O analysis. A simple list of method names and Big-O values is sufficient for the body of the document.

Note: since BetterMap is a subinterface of SimpleMap, the public members of SimpleMap are members of BetterMap. So, the text document should give Big-O values for all of the methods:

put

get

isEmpty

clear

size

containsValue

BetterMap Analysis:

The BetterMap interface contains the method containsValue. For the same of symmetry, one could assume that there would be a containsKey method as well, but it does not. There is a good reason this method is not included in the interface. Give the reason.

See the binary search tree notes for an algorithm for the remove method.

And here is the code I've written:

public interface BetterMap extends SimpleMap {

public boolean containsValue(Object value);

public V remove(Object key); }

====================================================================================

public class MyTreeMap implements BetterMap { /** * The size of this structure */ private int size; /** * The root of the binary search tree */ private BinaryTreeNode root;

public MyTreeMap(){ root = null; size = 0; }

@Override public void put(K key, V value) { if (key == null || value == null) throw new IllegalArgumentException("Key or value cannot be null"); helpPutTree(root, key, value); }

private void helpPutTree(BinaryTreeNode r, K key, V value) { if (r == null){ r = new BinaryTreeNode(key, value, null, null); size++; }

@SuppressWarnings("unchecked") int compare = r.key.compareTo(key); if (compare == 0) r.value = value; else if (compare > 0) helpPutTree(r.left, key, value); else helpPutTree(r.right, key, value); }

@Override public V get(Object key){ return helpGetTree(root, key); }

private V helpGetTree(BinaryTreeNode r, Object key) { if (r == null) return null; // Otherwise @SuppressWarnings("unchecked") int compare = r.key.compareTo(key); if (compare == 0) return r.value; else if (compare > 0) return helpGetTree(r.left, key); else return helpGetTree(r.right, key); }

@Override public boolean isEmpty(){ return size == 0; } @Override public void clear() { root = null; size = 0; } @Override public int size() { return size; } public boolean containsValue(Object value){ return helpContainsValueTree(root, value); } public boolean helpContainsValueTree(BinaryTreeNode r, Object value){ if(r == null){ return false; } else if(r.value == value){ return true; } else{ return helpContainsValueTree(r.left, value) || helpContainsValueTree(r.right, value); } } @Override public V remove(Object key) { return null; } }

======================================================================

public interface SimpleMap { public void put(K key, V value); public V get(Object key); public boolean isEmpty(); public void clear(); public int size(); }