Sets

Sequences are an abstract datatype representing the notion of ordered collections of objects of the same type. As before, this only tells us what the objects which inhabit this datatype look like, but not the operations that we can reasonably perform on them. To help with this, we can turn to the Set interface given below in the Java programming language:

/**

* The {@code Set} interface defines a minimal suite of operations that are to

* be support by the Set abstract data type.

*

* @param the type over which a {@code Set} is defined

*/

public interface Set {

/**

* Adds the specified object to the set.

*

* @param obj object to be added to the set

*/

void add(T obj);

/**

* Removes all of the elements from the set.

*/

void clear();

/**

* Returns {@code true} if the set contains the specified object and

* {@code false} otherwise.

*

* @param obj the object to find in the set

* @return {@code true} if the set contains the specified object and

* {@code false} otherwise

*/

boolean contains(T obj);

/**

* Returns {@code true} if the set is empty and {@code false} otherwise.

*

* @return {@code true} if the set is empty and {@code false} otherwise

*/

boolean isEmpty();

/**

* Remove the specified object from the set, if it is present.

*

* @param obj the object to remove

* @return {@code true} if the set contained the specified object and

* {@code false} otherwise

*/

void remove(T obj);

/**

* Returns the number of elements in the set.

*

* @return the number of elements in the set

*/

int size();

/**

* Returns an array containing all of the objects in the set in the proper

* order (from least to greatest).

*

* @return an array containing the objects in the set

*/

T[] toArray();

}

The second part of your project is to define a BinarySearchTree class which implements this interface. As in Part 1, there is no requirement to provide a definition for a toString() member function, this is left to your own discretion. Similarly, when implementing this interface, look for opportunities to generalize and simplify your implementation through the introduction of simplifying functions and procedures. Lastly, recall that the AVL-Tree datatype is an extension of a binary search tree. So when implementing your BinarySearchTree class, be mindful so that you design it to be reused for implementing a subsequent AVLTree.

Finally, keep in mind the invariant properties of a binary search tree, and use them as a guide in your implementation:

Every node has at most two children.

Consider any node X. Every node in the left subtree of X has a value less than X's, while every node in the right subtree of X has a value greater than X's.