Task 1 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). Step 1 Implement a binary search tree with integer-based nodes.

Step 2 Extend your BST by making a sub class of AVL or red-black tree utilising inheritance.

Step 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

Step 4 Present the user with a simple menu: Select an option: 1) Search for a number all data structures 2) Exit Enter in option (12): 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.