Description
Overview”
In this assignment, you will implement an abstract data type Set and its two subclasses TreeSet and HashSet. The Set class is a pure abstract super class, so you cannot create its instance. The actual set you will use in a program is an instance of either the TreeSet or the HashSet subclass. The TreeSet subclass implements the set abstraction using a binary search tree, while the HashSet does it by using a hash table. The TreeSet instance has a better worst case performance for updates. In contrast, the HashSet instance has a much better average case performance for search. ! Problem Statement” An abstract data type Set realizes the mathematical set, which is a collection of items with no duplicates. A set does not have a notion of order, unlike a list. Your task is to implement the Set type and support basic set operations such as union and intersection. The Set type is realized by three classes, the Set superclass and two subclasses TreeSet and HashSet. The complete declaration for the Set superclass is provided to you. Your task is to implement the concrete subclasses TreeSet and HashSet. You use some variation of a binary tree structure to implement the TreeSet subclass and a hash table for the HashSet subclass. You are not allowed to use any system library classes such as the vector or the list when implementing the internal data structure for the subclasses.! Specification” Here’s the declaration for the Set superclass.! ! class! Set { public! : //——— Update Operations —————————-// ! virtual void insert(string item) = 0; ! virtual void remove(string item) = 0; //——— Set Operations —————————-// ! virtual Set* set_union(Set* s2) = 0; //set union ! virtual Set* set_intersect(Set* s2) = 0; //set intersection virtual Set* set_diff(Set* s2) = 0; //set difference !! //——— Access Operations ——————–// ! virtual vector
