This is a C++ project.

For this programming lab, you are to implement the seven Dynamic Set Operators using a Binary Search Tree (BST). The name of your program MUST be BST.exe

The nodes for your tree will contain a string (the key), an integer (a piece of Satellite data, to count the number of times the string has been seen), and of course, left and right child pointers. You may implement the parent pointer, if you think it will help you implement your solution, but it is not required.

Your program will consist of a loop within main, which will accept commands from the keyboard, and execute them one-at-a-time. The commands your program must support are:

Note: the angle brackets shown above () are not to be used for input or output; theyre shown only to indicate that a string or a number () is to be input or output (see sample input/output below). All of your lines of output should end in a new line (

Sample input and output:

Your program should utilize good programming practices information hiding, etc. Your public methods should not give away HOW the BST works main() should never see your BSTs root pointer, for example. You will have to create some public methods that, in turn, call private methods to get the job done. Your dynamic set could just as easily be implemented with arrays, a linked list, or something else. What gives it its behavior is its interface; not its implementation!

insert ) If is NOT already in the set, add it to the set (and set the count to 1) In either case, send to cout delete If IS in the set, and has a count of more than 1, decrement the count corresponding to the string, and output , where nnn is the new count If IS in the set, and has a count of exactly 1, delete it from the set, and output search is in the set, output , where is the count for the string If is not in the set, output Output , where is the minimum value of the set. set is empty, output a blank line min If the Just like min, except output the maximum value of the set (or a blank line) max If is in the set, output ts successor . If doesn't have a successor, or if it isn't in the set, output a blank line next) If is NOT already in the set, add it to the set (and set the count to 1) In either case, send to cout delete If IS in the set, and has a count of more than 1, decrement the count corresponding to the string, and output , where nnn is the new count If IS in the set, and has a count of exactly 1, delete it from the set, and output search is in the set, output , where is the count for the string If is not in the set, output Output , where is the minimum value of the set. set is empty, output a blank line min If the Just like min, except output the maximum value of the set (or a blank line) max If is in the set, output ts successor . If doesn't have a successor, or if it isn't in the set, output a blank line next