test.cpp #include "MyTree.h" // Testing (you must implement yours for the perfomance studies) int main() { MyTree tree; // ... return 0; } assignment3.docx UCR - CS 010C Assignment 3 Deliverables:...

DUMMY


test.cpp #include "MyTree.h" // Testing (you must implement yours for the perfomance studies) int main() { MyTree tree; // ... return 0; } assignment3.docx UCR - CS 010C Assignment 3 Deliverables: Create a single PDF file that contains your answers to the questions. Then create a zip file that contains this PDF file along with all your code source files. Submit this zip file on iLearn. Deadline: 11/15/2020 11:59 pm. Use provided C++ skeleton files (MyTree.cpp, MyTree.h and test.cpp) to insert your code. 1. Implement a binary tree class MyTree using pointers (define struct BinaryNode to store internal nodes), where each node has a pointer to each of its children and to its parent, and each node holds two variables, a string myString and an integer myInt. Write functions in MyTree class to do the following: a. Insert(string, int): Insert new node into first available position (to keep the tree almost complete). E.g., To get full points your Insert functions should be faster than , where is the number of nodes in the tree. Hint: you may use additional private variable(s) in MyTree class. b. Preorder(): Output all strings in pre-order. c. FindMax(): Return a pointer to the node with maximum myInt. (If multiple nodes have the same maximum myInt, return any node.) d. MakeBST(): Convert the binary tree into a binary search tree (BST) with respect to myInt. That is, move around node values (myString and myInt) to satisfy the BST property. Do not change the structure of the tree (i.e. the pointers) but only swap myString and myInt values. (Hint: if you need to sort an array, you can use std::sort method; use std::swap to exchange the values of 2 variables) e.g., 2. What is the big-Oh complexity of your functions above? Also, what is the space complexity of your functions? Are they all in-place? If not, how much extra space do they need? 3. Test and measure the performance of your functions. Create sequences of 100, 1000, 10000, 100000 random (string, int) pairs and insert them into MyTree (using Insert() function). Measure the times (in nanoseconds or microseconds) to a) build the tree, b) execute Preorder(), c) execute FindMax(), d) execute MakeBST(). Report the times for each tree size in a table. Hint: To generate N random unique numbers, you can first create an array or a vector with N unique numbers (e.g., 1 to N), then use std::shuffle to rearrange them in a random order. MyTree.cpp #include #include "MyTree.h" MyTree::MyTree() : root_(nullptr), numNodes_(0) { // Initialize the tree without a root (empty tree) } MyTree::~MyTree() { // Delete all nodes except the root if (root_) { // Delete the root delete root_; } } BinaryNode *MyTree::Insert(const std::string &s, int x) { BinaryNode *node = new BinaryNode(s, x); // Insert the node return node; } void MyTree::Preorder() const { } BinaryNode *MyTree::FindMax() const { return nullptr; } void MyTree::MakeBST() { } MyTree.h #include #include typedef struct BinaryNode { std::string myString; int myInt; BinaryNode *parent; BinaryNode *left; BinaryNode *right; BinaryNode(const std::string &s, int x) : myString(s), myInt(x), parent(nullptr), left(nullptr), right(nullptr) {} } BinaryNode; class MyTree { public: MyTree(); ~MyTree(); // Delete all nodes in the tree size_t NumNodes() const { return numNodes_; }; // Insert new node into first available position (to keep the tree almost // complete), return the created node. BinaryNode *Insert(const std::string &s, int x); // Output all strings in pre-order // all the strings will be print in one line separated by spaces void Preorder() const; // Returns a pointer to the node with maximum myInt BinaryNode *FindMax() const; // Converts the binary tree into a binary search tree (BST) with respect to // myInt. That is, move around node values (myString and myInt) to satisfy the // BST property. void MakeBST(); private: BinaryNode *root_; size_t numNodes_; }; FOR DISCUSSION SHOULD BE AT LEAST 1 PARAGRAPH IN LENGTH (150 words) Quantity is IMPORTANT BUT QUALITY is Just as important. Say something deep & intuitive, don't just rephrase something you read or another student's posting Provide as much clarification to the issue as you can from credible sources. Health Costs Your company, like many others, is experiencing double digit percentage increases in health care costs. What suggestions can you offer that may reduce the rate of cost increases?