Sample 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 extends E> 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 void insert(int i);

}

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

}

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

// TODO Auto-generated method stub

}

/**

* Sorts an array using TreeSort with a specified BST

* @param tree tree to use

* @param a an array to sort

*/

}

import java.util.Collection;

import java.util.Iterator;

import java.util.TreeSet;

public class A3BSTree implements Tree{

private TreeSet tree;

private Node root;

public A3BSTree(){

tree = new TreeSet();

root = null;

}

public void add(E e) {

Node newNode = new Node(e);

if (root == null){

root = newNode;

} else {

Node currentNode = root;

if (currentNode.rightChild == null){

currentNode.rightChild = newNode;

} else {

}

}

tree.add(e);

}

@Override

public void addAll(Collection extends E> 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;

}

class Node {

E value;

Node leftChild;

Node rightChild;

public Node (E value){

this.value = value;

this.leftChild = null;

this.rightChild = null;

}

}

public static void main(String[] args) {

A3BSTree coolTree = new A3BSTree();

coolTree.add(34);

System.out.println(coolTree);

}

public void insert(int i) {

// TODO Auto-generated method stub

}

}

import java.util.Collection;

import java.util.Iterator;

import java.util.TreeSet;

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 extends E> 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;

}

public void insert(int i) {

// TODO Auto-generated method stub

}

}

Question 3: Name your class SortTester Take both of your tree implementations and compare them when used to implement a TreeSort sorting algorithm For numbers N= {10, 100, 1000, 10000, 100000, 10000001 a) Starting with unsorted arrays of N, measure how long it takes to sort such an array using regular BSTs and balanced AVL trees. b) Starting with reverse-sorted arrays of N, measure how long it takes to sort such an array using regular BSTs and balanced AVL trees. Produce the following table (the timing values below are just an illustration and do not relate to any real measurements) N 10: BST AVL BST (rev-sorted) AVL (rev-sorted) 213 ms 432 ms 543 ms 876 ms N 100: N 1000 : repeat for al values of N Save the result of your program execution in a file testrun.txt and submit it together with your other files