Question

In this task, you will need to compare how efficient it is to search three different data structures using a large data set. The structures we will use are list (C++ Standard Library linked list implementation), binary search tree, and a balanced BST of your choice (Adelson-Velsky and Landis Tree (AVL) or red-black tree). |

1 --> Implement a binary search tree with integer-based nodes
2 -- > Extend your BST by making a sub class of AVL or red-black tree utilising inheritance
3 --> #Include list in your main source file. Now insert 150,000 random numbers into a list, a BST, and a balanced BST (AVL or red-black tree). Make sure the same numbers are inserted into each. Reference the pseudocode below for guidance:

Initialise list numbers
Initialise BST bst
Initialise BalancedBST bbst
For num 1 to 150000
Set R to random number
Insert R into numbers
Insert R into bst
Insert R into bbst

4 --> Present the user with a simple menu:
Select an option:
1) Search for a number all data structures
2) Exit Enter in option (1–2

If the user selects 1, the user is asked to input a number. This number is searched for in the list, binary search tree, and balanced binary search tree, recording how long it takes in milliseconds to do each. If the number is found in the structures, display the time taken to find it in each structure. If not, let the user know that the number could not be found in any of them and still show the time to complete the search on each structure.

Answer 1

This task involves implementing a binary search tree with integer-based nodes, extending it by making a subclass of AVL or red-black tree utilizing inheritance, and including a list in the main source file. The next step is to insert 150,000 random numbers into a list, a BST, and a balanced BST (AVL or red-black tree). The same numbers must be inserted into each data structure.

After that, present the user with a simple menu with two options: search for a number in all data structures or exit. If the user selects the first option, ask the user to input a number. Then, search for the number in the list, binary search tree, and balanced binary search tree, recording how long it takes in milliseconds to do each. If the number is found, display the time taken to find it in each structure. If not, let the user know that the number could not be found in any of them and still show the time to complete the search on each structure.

Here is some pseudocode to help you get started:

// Step 1: Implement binary search tree with integer-based nodes

class Node {

int data;

Node* left;

Node* right;

};

class BinarySearchTree {

public:

BinarySearchTree();

~BinarySearchTree();

void insert(int data);

bool search(int data);

private:

Node* root;

};

// Step 2: Extend BST by making a subclass of AVL or red-black tree utilizing inheritance

// Step 3: Include list in the main source file and insert 150,000 random numbers

#include <iostream>

#include <list>

#include <cstdlib>

#include <ctime>

using namespace std;

int main() {

list<int> numbers;

BinarySearchTree bst;

BalancedBST bbst; // AVL or red-black tree

srand(time(NULL)); // Seed the random number generator

for (int i = 0; i < 150000; i++) {

int r = rand() % 150000 + 1; // Generate a random number between 1 and 150000

numbers.push_back(r);

bst.insert(r);

bbst.insert(r);

}

// Step 4: Present user with a simple menu

while (true) {

cout << "Select an option:" << endl;

cout << "1) Search for a number in all data structures" << endl;

cout << "2) Exit" << endl;

int option;

cin >> option