You are to construct and perform transversals on a binary search tree. Your algorithm must be written in the Java language and developed using the Jeliot algorithm animation environment. Your binary tree will contain a series of integers. Your algorithm must be able to accommodate a variable number of integers and all of these items must be entered by the user of the program by prompting for each integer from standard input. For the Jeliot development environment, you must use the scanner class that is supported by Jeliot to accomplish this. For more details see the help function in the Jeliot tool.

Your algorithm must take each integer entered by the user and insert it into a binary search tree. You can use either an array or linked list implementation to create your binary tree structure. When all of the values have been populated into the tree (you must figure out how to determine when the last value has been entered into your program), your algorithm must prompt the user for a search value, perform a search of your binary tree and report the number of iterations that were required to find the value.

As you will recall, the binary search reduces the number of iterations and compares by organizing values into a tree structure that incorporates a root value which is essentially the mid-point of the list of integers. Consider the following list of integers:

In this example, the root will be (array position 5) and the value of 6. Keep in mind that positions in the array begin at 0. If the search term were entered to be 2, then the midpoint would be selected which we would determine with the following formula:

midpoint = length of array / 2

Since the length is 11, the midpoint is position 5. We would then compare the search term 3 to the value in position 5 and since 3 < 6 the search will continue on the left side of the tree structure. We would repeat the process. With the following formula:

newbranch = current position / 2

The new length of the array is the left side of the tree up to the root which is 5. This new formula would yield position 2 which is the value 3. Since our search value is 2, it is less than the new branch of the tree meaning that our search value must be on the left of this branch. We repeat this process one more time:

newbranch = current position / 2

The current position is 2 so the new index position will be 1 which contains the value of 2. Our search term is 2 and the value in the new position is also 2 meaning that we have found the value we were looking for.

In this case our algorithm required 3 iterations to find the search term. The following code details the algorithm for the preceding example. You can use this code to further understand binary tree implementations and leverage some of the techniques that are supported within Jeliot, however, you cannot use this code as the basis for your assignment.

// // Example of an array based implementation of a binary search developed in the Jeliot tool // import Prog1Tools.IOTools; import java.util.*; public class binarySearchTree { public static void main (String[] args) { int iterations; // This variable counts the number of iterations of search that occur int index; // This variable identifies the node of the tree currently being searched int prev; // This variable will be used to keep track of the 'range' of the branch int searchValue; // This variable will contain the value we are searching for // // In this example we are using an array implementation of a binary tree and the array // is being pre-populated with the integers in the tree in the correct sequence. // in your assignment you must populate your binary tree by accepting values // from the user and populating a structure in the proper sequence using either // an array or linked list implementation // int bTree[] = { 1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,28, 29,30,33,34,35,36,37,38,39,40 }; // // Using Jeliot, you can use the System.out.println method to output information // to the console. // System.out.println("Enter an integer between 1 and 40 to search for:"); // // Using Jeliot, you must use the scanner class to get input from the user as // illustrated below. // Scanner in = new Scanner(System.in); searchValue = in.nextInt(); iterations=1; // // In this section we set the initial midpoint of the array which is the root value // index=bTree.length /2; prev=bTree.length; // // Here we call the binary search method which is designed to recursively // search until the proper value has been found // binarySearch(bTree, index, prev, searchValue, iterations); } public static void binarySearch(int[] bTree, int index, int prev, int searchValue, int iterations) { // // If our search value is smaller then the current position then // we need to search the left branch of the tree. The index value // indicates the current node that is being compared with the search value // the prev value is used to help identify the width of the current branch // so that we can identify the next branch to follow down. // if (bTree[index] < searchValue) { index = (prev-index)/2+index; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // If our search value is larger than the current position then // we need to search the right branch of the tree. Note that in each // iteration of the search we recursively call binarySearch which searches // the next level down in the tree. // else if (bTree[index] > searchValue ) { prev = index; index = index / 2; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // When the search value is found, print the number of iterations the search // took to the console and exit the binarySearch method // else { System.out.println("Found search value in:"+iterations+" iterations"); return; } } }

In the preceding example, the tree values were created in sequence meaning that the array was populated with values in order. Your algorithm must be able to accommodate values entered in any sequence which means that you must be able to adjust the structure of the tree as the root value and other values change.

In the example above, we have an array that forms the basis of our binary search tree. We determine the root by looking midway through the array. The example above has an advantage in that the array is already in sorted order. In your algorithm you will not have that advantage.

When you have completed your algorithm and your Asymptotic analysis of your algorithm please run it several times within Jeliot and observe the results. Use the following values for both the contents of the binary search tree and the search value:

Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14, 9, 8, 6, 11

Search value: 9

Is the time (expressed in the number of iterations required to complete a search) consistent with your Asymptotic analysis in worst case (Big O)?

As part of your assignment, you must submit both a description of the assignment and how your algorithm works including an Asymptotic analysis of your algorithm. Your analysis must include the efficiency of your algorithm expressed in Big Oh notation. The scope of your asymptotic analysis should only include the binary search portion of your assignment.

Further, as part of your assignment, you must include the code of your algorithm. All of these elements of this assignment must be completed and posted to the assignment for Unit 4 by the end of the week for unit 4. Finally, you must include a screen shot or other capture of the output of you binary search tree that indicates the number of iterations that were required to find the search value.

During Unit 5, you must review the work of at least three of your peers. As part of your review, you must copy and paste your peers code into the Jeliot tool and execute it. If the code does not function properly you should make suggestions on how to correct the problems (if possible). If the efficiency of the algorithm can be improved you should make these suggestions. You should coordinate with your fellow student and follow up on any corrections they make by re-running the code and providing additional feedback.

As you review your own algorithm and those of your peers, you should be looking for the following characteristics that our text outlined as being requirements of a good algorithm.

It must provide the correct output based upon the input

It must be composed of concrete steps

There can be NO ambiguity of the flow of the algorithm

The algorithm must have a finite number of steps that is determinable

The algorithm must terminate or complete