The files Set.h and Map.h define the exhaustive set of methods students must implement. The file BinarySearchTree.h has a boiler-plate already built with the required functions, so students need only provide their unique code. The BinarySearchTree must demonstrate O(log n) behavior for get, insert, and remove when working with a balanced number sequence. The timing for this structure will be unavoidably deplorable when inserting a series in-order, however, and students are under no expectation to solve that problem. This data structure will break down with in order key sequence insertions, and that is expected. ifndef PROG2_BINARYSEARCHTREE_H #define PROG2_BINARYSEARCHTREE_H #include #include "Map.h" namespace sdsu { template class BinarySearchTree : public Map { // The BST links together BSTNode objects. The outside world never // needs to use these, but this data structure will use them to build // the search tree. struct BSTNode { // The BST structures itself around the KEY's ranking. The key is // so important, it must be unique in the BST. KEY key; // The value will almost certainly not be a void*, but this allows // us to store ANYTHING, for we can cast a void* into something else // void* is an address to anything . . . not nothingness. Values // in a map may be repeated, and values don't appear in a Set. VALUE value; std::shared_ptr childL; std::shared_ptr childR; BSTNode(){}; BSTNode(KEY item) : key(item), childL(nullptr), childR(nullptr){}; std::pair&, int> keyset(std::shared_ptr &arr){ std::pair&,int> toRet(arr); }; // This is something like Java's toString method. // This is an IN-ORDER traversal. friend std::ostream& operator< root; int curSize; // this function may help when you write other functions. Sometimes you // wnat to literally work with the node holding the key, and not // just the keys and values themselves. Your design will decide if you // need something like this or not. // BSTNode &getNode(const KEY &key){} // This is a PRIVATE version of teh insert function that no one on // the outside can call. I find it useful for something like // the public version to kick things off, and this does the real // work. bool insert(const KEY &key, std::shared_ptr &start) { curSize++; return true; } public: BinarySearchTree() : curSize(0){ } BinarySearchTree(const BinarySearchTree &other) { } ~BinarySearchTree() override { } bool contains(const KEY &key) const override { return false; } void clear() override { } virtual VALUE &get(const KEY &key) override { VALUE &val = (root->value); return val; } bool insert(const KEY &key) override { return insert(key, root); } VALUE insert(const KEY &key, const VALUE &val) override { return val; } std::pair,int> keys() override{ KEY* raw = new KEY[size()]; std::shared_ptr arr = std::make_shared(raw); // Todo: Extra Credit Students fill up the arr[] with the keys in-order std::pair,int> toRet(arr,size()); return toRet; }; virtual std::pair,int> values() override { VALUE* raw = new VALUE[size()]; std::shared_ptr arr = std::make_shared(raw); // Todo: Students fill up the arr[] with the values in-order // Todo: with respect to their keys (not each other). Extra Credit std::pair,int> vals(arr,size()); return vals; }; bool remove(const KEY &key) override { curSize--; return false; } int size() const override { return curSize; } VALUE& operator[](std::size_t idx){ return get(idx); } friend std::ostream& operator< const &bst) { if( bst.root != nullptr ) return os << "[" << (*bst.root) << "]"; return os; } }; } #endif //PROG2_BINARYSEARCHTREE_H