Sets Sequences are an abstract datatype representing the notion of ordered colle
ID: 3598967 • Letter: S
Question
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<T> 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 <T> the type over which a {@code Set} is defined
* @version 1.0
*/
public interface Set<T> {
/**
* 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<T> 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<T> class, be mindful so that you design it to be reused for implementing a subsequent AVLTree<T>.
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.
Explanation / Answer
For the first part of the question:
As sequences are an abstract datatype representing the notion of ordered collections of objects of the same type and it is advised to build a set<T> interface which has following basic operations involved with it: add element, remove element, clear the set, check whether the set is empty or not, check whether the set contains a particular element or not. These things almost reflect the basic operation of a much nurtured abstract data type called 'Queue'. Before going into the code snippets here is what I have tried to achieve:
To have a class Set, which has an array, called set (that basically behaves like a 'Queue') and the above-mentioned operations are performed by means of function on that array. The set has a maximum length of 'size' and has a start and end pointers (just like a queue). The variable 'len' stores and updates the current length of the array:
protected int set[] ;
protected int start, end, size,len;
Here a constructor initializes any object of type 'Set' as:
public Set(int n) // Constructor
{
size = n;
len = 0;
set = new int[size];
start = -1;
end = -1;
}
Here is the program written in Java:
class Set{
protected int set[] ;
protected int start, end, size, len;
public Set(int n) // Constructor
{
size = n;
len = 0;
set = new int[size];
start = -1;
end = -1;
}
public void add(int n) // Adds the specified object to the set.
{
if (end == -1)
{
start = 0;
end = 0;
set[end] = n;
}
else if (end + 1 >= size)
throw new IndexOutOfBoundsException("Overflow Exception");
else if ( end + 1 < size)
set[++end] = n;
len++ ;
}
public void clear()
{
set = null;
start = end = -1;
}
public boolean contains(int k)
{
int i;
for(i=1;i<len;i++)
{
if (set[i] == k)
{
return true;
}
}
return false;
}
public boolean isEmpty()
{
if(len ==0)
return true;
else
return false;
}
public void set2array()
{
if(start != end)
{
for(int i=0;i<len;i++)
System.out.println(set[i]+" ");
}
if(end == start)
System.out.println("No item");
}
}
I used a main function to implement the class Set:
public class Chegg_Set {
public static void main(String[] args) {
Set s1 = new Set(50); //initialize a object 's1' of class type 'Set' with the use of constructor
int n=56, m=89;
s1.add(n);
s1.add(m);
System.out.println("Items are");
s1.set2array();
System.out.println(s1.contains(m));
s1.clear();
s1.set2array();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.