Consider the following BST class definition for a Binary Search Tree data structure. This BST is different (from the textbook explanation) in that it removes elements in the leaves but not those in the internal nodes. When deleted, the values in the internal nodes are marked as inactive. These nodes remain in the tree. The accompanied compress method removes all the inactive nodes from the tree.

 template struct Node { Node(const T& v) : m_val(v), m_act(true), m_left(0), m_right(0) {} T m_val; bool m_act; Node* m_left; // pointer to the left subtree. Node* m_right; // pointer to the right subtree. }; template class BST { public: BST(); BST(const BST&); void operator=(const BST&); ~BST(); bool remove(const T&); void insert(const T&); bool is_member(const T&) const; long size() const { return m_active; } void compress(); // removed all marked nodes. Bag sort() const; // produce a sorted Bag. private: Node* m_root; long m_active; // count of active nodes. long m_inactive; // count of inactive nodes. }; 

To test your implementation, produce the following main program using your implementation of BST:

Generate 300 student records randomly into a Bag b1. Iterate on b1 to subsequently insert the obtained values to BST t1. Remove 100 student records randomly from b1 and the same elements from t1. Verify if remaining contents of b1 and t1 are identical (by matching both).

Generate 500 students randomly into a Bag b2 and BST t2, likewise. Remove 300 student records randomly from b2 and the same elements from t2. Call compress() just after every 50 removals from t2. Afterword, verify if the remaining contents of b2 and t2 are identical.

Use ssid field for the search key of the student record. Bag can be any of your past implementation.