## Question

This assignment is designed to give you some practice working with recursion and trees.

This assignment is done using Eclipse.

Import the .zip file that is provided and when it is complete, export it again as a .zip.

Submit solutions to question 3 (no GUI testers required this time but you can do them if you want) only but do ALL questions to prepare yourself for the tests.

Question 3: Perform simulations to compare the performance of searching using sequential search and a binary search tree.

You will need to generate two disjoint groups of integers (use random number generators): Group A with at least 100 integers and Group B with at least 10,000 integers.

Use arrays to save both groups.

a- Insert the integers from Group B into a binary search tree, and compute its height.

b- For each integer in Group A, search for it in both the array containing Group B and in the binary search tree.

This case represents unsuccessful searches. Count the number of comparisons made in each case for the 100 searches and record them into a table.

c- Randomly choose 100 integers from Group B and search for them in both the array containing Group B and in the binary search tree.

This case represents successful searches. Count the number of comparisons made in each case for the 100 searches and record them into a table.

Now, your table contains the number of comparisons needed to search for 200 values (100 unsuccessful, and 100 successful searches) for both sequential search and binary search tree.

Compute the average and standard deviation of each case. Comment on the results.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package question3;import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

public class Question3 {

private static int arraySearch(int[] array, int value) {

int index;

for (index = 0; index < array.length; index++) {

if (array[index] == value) {

return index + 1;

}

}

return index;

}

private static double arrayAverage(int[] array) {

int total = 0;

for (int x: array) {

total += x;

}

return (total * 1.0) / array.length;

}

private static double arrayStandardDeviation(int[] array) {

double total = 0.0;

double mean = arrayAverage(array);

for (int x: array) {

total += Math.pow(x - mean, 2);

}

return Math.sqrt(total / array.length);

}

private static void printSearches(int[] array) {

System.out.println("Average: " + String.format( "%.2f", arrayAverage(array)) );

System.out.println("Standard Deviation: " + String.format( "%.2f", arrayStandardDeviation(array)) + "\n");

}

public static void main(String[] args) {

List<Integer> numbers = new ArrayList<Integer>();

for (int i = 1; i <= 100000; i++) {

numbers.add(i);

}

Collections.shuffle(numbers);

System.out.println("Creating Group A array with 100 integers...");

int[] groupA = new int[100];

for (int i = 0; i < groupA.length; i++) {

groupA[i] = numbers.remove(0);

}

System.out.println("Creating Group B array with 10,000 integers...");

int[] groupB = new int[10000];

for (int i = 0; i < groupB.length; i++) {

groupB[i] = numbers.remove(0);

}

System.out.println("Inserting the integers from Group B into a binary search tree...");

BST tree = new BST();

for (int i = 0; i < groupB.length; i++) {

tree.insert(groupB[i]);

}

System.out.println("The height of the Binary Search Tree is: " + tree.height() + "\n");

System.out.println("Performing 100 unsuccessful searches on array...");

int[] arrayUnsuccessf...