(Solved): I need:1. codes (implementations of two different BBSTs) can pass the Online Judge System2.generator ...

Learning Outcomes Enhance coding skills through practices Implement the most popular types of balanced binary search trees (BBSTs): • Evaluate and compare similar BBSTs and find their strengths and weaknesses: Learn how to select appropriate data structures to solve problems. 1 Overview You are required to maintain a multiset S, which supports the following operations: 1. Insert a numbers to : 2. Erase a mumber equal to x from Sif exists; 3. Find the order of r in S, i.e., 1 + deslv < x); 4. Find the r-th smallest mumber in S; 5. Find the precursor of a number x in S. i.e., max {v} if exists: 6. Find the successor of a number r in S. i.e. min {u} if exists. VES, DES,U> 2 Detailed Requirements 2.1 Select BBSTS In this assignment, you are asked to select and achieve any two kinds of BBSTs mentioned or introduced in the lecture (preferably Splay and AVL Tree) to achieve the operations listed above. You need to submit your implementations to the Online Judge System and pass the corresponding question BBST. 2.2 Efficiency Analysis and Study Report You will be the problem setter this time to design the test data for this problem. You are required to compare and analyse the differences in efficiency between different BBSTs by feeding the different types of testing data designed and generated on your own for the operations mentioned above. The generator programs should be written 1 in C++, and the data you generated should meet the constraints in the problem description. A sample generator is available on canvas Then, you need to write a report to brief your progress and findings on this assignment. The following things should be clearly stated in the report: • The compiling command for compiling your generator programs, c.g-g++ sampleGenerator.cpp -o exec file. Some available compiling options are -std=c++11, -1m, -02; . An explanation about the strategy and purpose of the test data sets you designed and generated; . An analysis of the performance of the different BBSTs under your different data sets; • A conclusion including the strengths and weaknesses of the BBSTs you implemented based on the performance analysis. 3 Assessment Criterion You will be assessed by how much and how well you can apply what you have learnt from the course, some considerations are: . Whether you successfully implemented exactly two kinds of the BBSTs and your programs passed the problem in the Online Judge System; • To what extent the data generated by your generator programs matches the design stated in your report: • To what extent the data sets you designed and stated in your report can reveal the characteristics of the BBSTs. For example, if you implemented a Splay tree, you may think about under which kind of special data it will perform well; • How comprehensively you compared the performance of different BBSTs under your test data; • To what extent your conclusion matches the performance of your implementations under the test data and how comprehensively you analysed the strengths and weaknesses of your BBSTS. 4 Hints . One reasonable standard for assessing the performance of the BBSTs is the number of rotations during the whole process . You may start with a further research about the BBSTs by reading some references. BBST Description You are required to maintain a multiset S, which supports the following operations 1. Insert a number 2 to S 2 Erase a number equal to a from Sif exists: 3. Find the order of 2 in S. ie. 1 + Deslu