Binary Search Trees (BST) are data structures that store items (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key. The Tree interface provides three methods to add and remove elements to and from the tree. It also provides an iterator that visits the elements in-order, as well as a function height that simply returns the height of the tree. Note that the speed of these operations may strongly depend on the implementation. In this assignment, you will have to write two implementations of Tree interface (provided), one that uses regular (possibly unbalanced) Binary Search Trees , and one that uses balanced AVL Trees . After that, you will have to test the performance of TreeSort when using your implementations. For your convenience, some starting code is provided. Note that it either does not implement some features or implements them improperly.

Question 1:

Implement the necessary methods in the two implementations (called A3BSTree and A3AVLTree) of Tree interface:

public void add(E e);

public void addAll (Collection c);

public boolean remove(Object o);

public Iterator iterator();

public int height();

public int size();

The classes should use generics. The AVL add and remove operation should keep the tree balanced. It should also be possible to have duplicate items in the trees (something that binary search trees normally do not allow); think about how you can work around it. You are free to implement any private or protected methods and classes as you see needed. However, you may not have any public methods other than the ones mentioned (or the ones present in the interface or its super classes).

Skeleton of the code:

import java.util.Collection; import java.util.Iterator; public interface Tree  { /** * Adds the specified element to this tree (duplicates are allowed) * @param e element to add */ public void add(E e); /** * Adds all of the elements in the specified collection to this tree. * (duplicates are allowed) * @param c Collection containing the elements */ public void addAll (Collection c); /** * Removes the specified element from this set if it is present. * (if more than one were present, removes only the first one) * @param o object to remove * @return true if this tree contained the element */ public boolean remove(Object o); /** Returns an iterator over the elements in this tree in ascending order * @return the iterator described above */ public Iterator iterator(); /** Returns the height of the tree. * For an empty tree should return -1. * For a tree of one node should return 0 * @return height of the tree */ public int height(); /** Returns the number of elements in the tree. * @return number of elements */ public int size(); }