Binary Search Tree (Java) ------------------------- 1. Implement a java class 'BinarySearchTree' with dynamic memory allocation. It should implement methods to: +Search for key: Returns pointer to the node containing the key (or 0 if not found) and the number of comparisons made to find it. + Insert key (integer) + Write a function that produces a binary tree search from N random numbers. 2. Repeat the above implementing the tree with a 1-dimension array of N numbers 3. Implements class "linked list" with dynamic memory allocation and the same set of methods. 4. Inserted into each of the above 3 classes 1000 keys and then make 100 searches for keys that do not exist. Measure the average number of comparisons performed in each case. 5. Repeat the same for N = 1000, 10000,30000,50000,70000,100000,150000 .. as much as the computer can withstand 6. Make a chart showing the number of comparisons required VS N for each of the above 3 classes. 7. Discuss the results. It's what you expect based on theory ? What structure is faster and why? Part 2 - File sorting --------------------- Create a file N = 900Mbytes with random integers on disk and sort it directly to disk using only M = 100Mbytes of memory (u can choose other sizes, e.g. 90Mbytes file / 10MByte RAM). Sort the file by the method described in [url removed, login to view]: You can re-use code on the internet but do not make complete copy&paste - at least rename method/variable names!