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.
. 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 a
ay, 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, XXXXXXXXXXrandom (string, int) pairs and insert them into MyTree (using Insert() function). Measure the times (in nanoseconds or microseconds) to
a) build the tree,
) 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 a
ay or a vector with N unique numbers (e.g., 1 to N), then use std::shuffle to rea
ange 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-orde
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?