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 2:

Name your class TreeSort. The class should have the following methods:

public static void sort( E[] a);

public static void sort(Tree tree, E[] a);

Skeleton of the code:

import java.util.Arrays; import java.util.Iterator; public class TreeSort{ /** Sorts an array using TreeSort with a balanced BST implementation * @param a an array to sort */ public static void sort( E[] a){ Tree tree = new A3AVLTree<>(); sort(tree, a); } /** * Sorts an array using TreeSort with a specified BST * @param tree tree to use * @param a an array to sort */ public static void sort(Tree tree, E[] a){ //to do } } 

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

public class A3AVLTree  implements Tree{ private TreeSet tree; public A3AVLTree(){ tree = new TreeSet<>(); } @Override public void add(E e) { tree.add(e); } @Override public void addAll(Collection c) { tree.addAll(c); } @Override public boolean remove(Object o) { return tree.remove(o); } @Override public Iterator iterator() { return tree.iterator(); } @Override public int height() { return 0; } @Override public int size() { return 0; } }