How do I modify the benchmark.cpp below so that I can compare the runtime of BST and RBT? Thanks for you help!

#include

#include

#include

#include

#include

#include "util.hpp"

using namespace std;

int main() {

// This is an example of runtime benchmarking

// TODO (final): Replace the following with a benchmarking comparison

// of two data structures, as described in the project instructions

int numTrials = 100;

int dataSize = 3000;

vector times(numTrials, 0);

Timer t;

default_random_engine generator;

uniform_real_distribution distribution(-1.0, 1.0);

// Run benchmarks and time each trial

for (int trialIndex = 0; trialIndex

// Set a new random seed

generator.seed(1 + trialIndex);

t.begin_timer();

double total = 0.0;

for (int dataIndex = 0; dataIndex

double currentRandom = distribution(generator);

total += currentRandom;

}

times[trialIndex] = t.end_timer();

}

// Compute statistics from trial times

double totalTime = 0.0;

for (int i = 0; i

totalTime += times[i];

}

double meanTime = totalTime / ((double) numTrials);

cout

cout

return 0;

}

Let me know if you need util.hpp/util.cpp. Thanks once again.

EDIT:

util.hpp

#ifndef UTIL_H

#define UTIL_H

#include

#include

#include

#include

using std::istream;

class Timer{

private:

/* start the timer */

std::chrono::time_point<:chrono::high_resolution_clock> start;

public:

/*

* Function called when starting the timer.

*/

void begin_timer();

/*

* Function called when ending the timer. Returns duration in nanoseconds

* PRECONDITION: begin_timer() must be called before this function

*/

long long end_timer();

};

class Utils{

public:

/*

* Load all lines from istream `in` into the vector `v`

*/

void static load_vector(std::vector<:string>& v, istream& in);

/*

* Load the specified number of lines from istream `in` into the vector `v`

*/

void static load_vector(std::vector<:string>& v, istream& in, unsigned int num_lines);

};

#endif //UTIL_H

-------------------------------------------------------------------------

util.cpp

#include

#include "util.hpp"

using std::istream;

using std::endl;

using std::cout;

using std::string;

using std::vector;

/*

* Starts the timer. Saves the current time.

*/

void Timer::begin_timer()

{

start = std::chrono::high_resolution_clock::now();

}

/*

* Ends the timer. Compares end time with the start time and returns number of nanoseconds

*/

long long Timer::end_timer()

{

std::chrono::time_point<:chrono::high_resolution_clock> end;

end = std::chrono::high_resolution_clock::now();

return (long long)std::chrono::duration_cast<:chrono::nanoseconds>(end - start).count();

}

/*

* Load all lines from istream `in` into the vector `v`

*/

void Utils::load_vector(vector& v, istream& in)

{

string line = "";

while (true) {

getline(in, line);

if (in.eof())

break;

v.push_back(line);

}

}

/*

* Load the specified number of lines from istream `in` into the vector `v`

*/

void Utils::load_vector(vector& v, istream& in, unsigned int num_lines)

{

string line = "";

for (unsigned int i = 0; i

getline(in, line);

if (in.eof()) {

std::cout

break;

}

v.push_back(line);

}

}

Task 3: Data structure benchmarking comparison For this task, you will empirically test the following two claims A naive (non-self-balancing) BST and a red-black tree both have O(log n) average-case runtime performance for the operations insert(element) and find(element), under the assumption that all insertion orders are equally likely A naive (non-self-balancing) BST has O(n) worst-case runtime performance for the operations insert(element) and find(element), whereas a red-black tree has O(log n) worst-case runtime performance for the same operations You do not need to submit a zip file or GitHub repository containing code for this task (but please do keep using Git to develop your code!). Instead, you will submit a PDF document containing a written analysis of your results You may reuse your BST implementation from PA1. For red-black trees, you may use the built-in C++ container std::set. If you think that your original BST implementation was incorrect or unnecessarily inefficient, you may modify or improve it for this project, but you should not transform it into a self-balancing tree; the point is to compare a self-balancing implementation (red-black trees, via std::set) to a non-self-balancing implementation (your BST code from PA1). We recommend putting your benchmarking code in src/benchmark/benchmark.cpp and compiling it with make benchmark. Note that we have provided some timer and I/O utilities in src/benchmark/util.hpp. To use your your BST implementation, copy your completed version of BST.hpp, BSTIterator.hpp, and BSTNode.hpp into the directory src/benchmark, and then use #include "BST .hpp". To access the built-in red-black tree implementation, use #include