Bags, Trees and Performance

BACKGOUND For this piece of work there will be a need for a bag data type. A bag is defined as a collection of items of the same type, with the following methods: 1) Create a new bag 2) add an element to the bag 3) count how often a specified item appears in the bag 4) count how many items are in the entire bag 5) print the contents of the bag PART A: IMPLEMENTATION 1)Create a template Binary Search Tree class TBST. you should adapt the code supplied. NOTE: you do not need to implement the deleteFromBST function. 2) Use TBST to implement a bag class (TBag) that holds characters. PART B: DISCUSSION 1) Compare your implementation in PART A with the array-based approach also supplied. you should discuss Bid(O) time and space growth rates, and any other performance factors you consider important 2) The TBag could also be implemented using the STL List class. Outline such an implementation, and discuss how this might affect the bag's performance. NOTE: you are not required to provide woking code in this case. 3) Briefly discuss why neither of the above implementatons work for all types of data, and suggest a change to your implementation to achieve a completely general template ## Deliverables 1) Complete and fully-functional working program in executable form as well as complete source code of all work done. The source code should be implemented as outlined in PART A of description 2) All three written components dicussing as outlined in PART B of description ## Platform unix or windows