CSC 204 Binary Search Trees Extra Credit 5- Algorithm Design & Analysis

Instructions:

1) Implement the generate_gure() function in binary_search_tree.py. This is the only place you should be writing any code in the entire le. In this function you should generate a gure that will have three line plots to compare linear search with binary search. These line plots should be as follows:

(i) The average case running time of linear search on arrays of varying length.

(ii) The average case running time of binary search on completely skewed binary search trees of varying size.

(iii)) The average case running time of binary search on binary search trees of varying size that are created by inserting elements in random order. (these trees should be more balanced).

2) Write a few sentences describing what you see in your gure and why. Your explanation should involve a brief discussion of asymptotic complexities. 

Notes: I have implemented for you all the code you will need to build a binary search tree, search a binary search tree, and to perform linear search on an array. To build a binary search tree you can use the following code
          tree = build_binary_search_tree(keys)

where keys is an array of the keys to be inserted into the tree. These keys will be inserted into the tree in the exact order they are in the array. In order to then search for a key in the binary search tree you can use the following code
               tree.search(key)

To run linear search you can use the following code
                    linear_search(A, key)

where the first argument, A, is the array to search, and the second argument, key, is the key to search for.