You will implement a binary search tree data structure in C++, and turn in a program evaluating the data structure. Implement a templated Binary Search Tree data structure, implementing the following functionality:

Add(value to insert)

Delete (delete given node, restructure sub-tree)

Maximum(Find Maximum Key)

To evaluate this data structure, write your program to read from an array of unsorted integers. You could also read from a data file (with the filename passed as a command line parameter) and populates the data structure. Rigorous testing is expected! Be sure to include tests for attempting to remove a node from an empty BST, attempting to insert a duplicate node, removing a node with no children, removing a node with one child, and removing a node with two children. Be sure to verify the BST organization and structure are correct.

BONUS - Performance Analysis of your Binary Tree Conduct a performance analysis of your BST and record the amount of time it takes to do Add and Remove the following: 100 nodes 1000 nodes 10000 nodes 100000 nodes Display your data in a data table and graph the results.

BONUS - Self-Balancing Binary Search Tree Implement a Self-Balancing Binary Search Tree (Links to an external site.)Links to an external site.. Evaluate the performance of this data structure as compared to the normal binary search tree on adding and removing 100, 1000, 10000, and 100000 nodes.