#pragma once #include #include

namespace cop3530 {

template class bst { struct node { // key Key key // value T=t; // left child node *left = NULL; // right child node *right = NULL;

node() {} node(Key k, T t):key(k), t(t) {} };

// root of tree node* root = NULL;

}

public: bst(); ~bst(); void insert(const Key &key, const T &t); void erase(const Key &key); T& at(const Key &key); bool contains(const Key &key) const; bool empty() const; size_t size() const; std::vector> inorder_contents(); std::vector> preorder_contents();

};

template bst::bst() { root = NULL; }

template bst::~bst() { delete root; }

template void bst::insert(const Key &key, const T &t) { //add code here }

template void bst::erase(const Key &key) { //add code here }

template T& bst::at(const Key &key) { //add code here }

template bool bst::contains(const Key &key) const {

//add code here return false; }

template bool bst::empty() const { if (root != NULL){ return false; } else { return true; } }

template size_t bst::size() const {

//add code here return 0; }

template std::vector> bst::inorder_contents() { std::vector> contents;

//add code here return contents; }

template std::vector> bst::preorder_contents() { std::vector> contents;

//add code here return contents; }

}

Thank you!

Overview You will implement a templated binary search tree (BST). You will then use your BST to create a program to track student information at a college. Lastly, you will consider what changes will be necessary to change your unbalanced BST implementation to a self-balancing Adelson Velsky and Landis (AVL) Tree. Structure This project is broken up into two parts: 1. Complete the BST interface 2. Complete the student_db interface 3. Answer the questions for the PAlb design document. Complete the Interfaces Start by downloading the project zip folder from Canvas and extract it. You can use any text editor to open the project source files. As with PAO, If you are using an IDE like Visual Studio or Clion, toke core that you are only using it to edit the source files, not to compile and run the code. You must do that on the terminal using the provided makefile (covered in the next section). When completing the Interface, you may add new public or private functions or member variables. However, you may not modify or remove existing functions or member variables. Additionally, you may not change the way the tests are written. E.g. You may not modify the tests so that a new function you create is called in the test case. Do not create a main function. The testing framework will generate it automatically. You may use anything in the C++ STL to complete the project. We encourage you to explore the new features added in the C++11, C++14, and C++17 standards, such as smart pointers. bst Interface Details The bst class represents an unbalanced binary search tree. Key and T refers to the key type and value type specialization of the templated deque. Method Description | bs10: Constructs abst object, initializing necessary member variables, etc -- - Destructs the bst object. Should free any dynamically allocated memory. vold Insert(const Key Skey, const T &t; Inserts new node into the bst, mopping key to t If a nade with key key is already present in the bst. t replaces the previously tapped valve vold erese(const Key Skeyli Removes the node with key key from the bst Throws on stdout of range error if anode with Key key is not found in the bst. bool contains const Key Skeyli Returns true to node with key key is present in the bst and false otherwise. T& cffconst Key &keyla Returns a reference to the value type to which key node with Throws on stout_of_range error if key key is not found in the bst. bool empty() const size_t sized const std::vector<:pair t>> inorder_contents: Returns true if the bst is empty and false otherwise. Returns the number of nodes in the bst Performs an inorder traversal of the bst and returns the contents as a vector of pairs. Each pair's first element should be the key of the corresponding bst node and the second element should be the value of the corresponding bst node. See the test cases for details on the format expected. Performs a preorder traversal of the bst and returns the contents as a vector of pairs. Each pair's first element should be the key of the corresponding bst node and the second element should be the value of the corresponding bst node. stduvector> preorder contents: Overview You will implement a templated binary search tree (BST). You will then use your BST to create a program to track student information at a college. Lastly, you will consider what changes will be necessary to change your unbalanced BST implementation to a self-balancing Adelson Velsky and Landis (AVL) Tree. Structure This project is broken up into two parts: 1. Complete the BST interface 2. Complete the student_db interface 3. Answer the questions for the PAlb design document. Complete the Interfaces Start by downloading the project zip folder from Canvas and extract it. You can use any text editor to open the project source files. As with PAO, If you are using an IDE like Visual Studio or Clion, toke core that you are only using it to edit the source files, not to compile and run the code. You must do that on the terminal using the provided makefile (covered in the next section). When completing the Interface, you may add new public or private functions or member variables. However, you may not modify or remove existing functions or member variables. Additionally, you may not change the way the tests are written. E.g. You may not modify the tests so that a new function you create is called in the test case. Do not create a main function. The testing framework will generate it automatically. You may use anything in the C++ STL to complete the project. We encourage you to explore the new features added in the C++11, C++14, and C++17 standards, such as smart pointers. bst Interface Details The bst class represents an unbalanced binary search tree. Key and T refers to the key type and value type specialization of the templated deque. Method Description | bs10: Constructs abst object, initializing necessary member variables, etc -- - Destructs the bst object. Should free any dynamically allocated memory. vold Insert(const Key Skey, const T &t; Inserts new node into the bst, mopping key to t If a nade with key key is already present in the bst. t replaces the previously tapped valve vold erese(const Key Skeyli Removes the node with key key from the bst Throws on stdout of range error if anode with Key key is not found in the bst. bool contains const Key Skeyli Returns true to node with key key is present in the bst and false otherwise. T& cffconst Key &keyla Returns a reference to the value type to which key node with Throws on stout_of_range error if key key is not found in the bst. bool empty() const size_t sized const std::vector<:pair t>> inorder_contents: Returns true if the bst is empty and false otherwise. Returns the number of nodes in the bst Performs an inorder traversal of the bst and returns the contents as a vector of pairs. Each pair's first element should be the key of the corresponding bst node and the second element should be the value of the corresponding bst node. See the test cases for details on the format expected. Performs a preorder traversal of the bst and returns the contents as a vector of pairs. Each pair's first element should be the key of the corresponding bst node and the second element should be the value of the corresponding bst node. stduvector> preorder contents