Binary Search & AVL Trees

Part 1. You are to write a main program that will use the BST ADT to determine its search performance characteristics for different sized trees. The program shall report timing data that you can then analyse and derive an approximate complexity function. Proceed as follows: 1. Construct a binary search tree, having coded a suitable comparison function. You can use simple integers if you wish. These can be passed directly to the BST by casting them to type (void *) and similarly casting them back to integers within the compare function. 2. We are primarily interested in the search performance of the BST as a function of the number of items or nodes in the tree. Therefore your program needs to progressively add more and more items to the BST. It is suggested that you add 10,000 items initially and for each timing run add a further 10,000 items up to a total of a 100,000 items. The key values should also be stored in a separate array so that you can use them for the search testing. You can use the rand library function to generate keys but note: a. There is no guarantee that rand will produce unique integers. You must test the return value from BstInsert to see if it successfully inserted a new key value or not, otherwise try again with a different random key value. b. On some systems the maximum value returned by rand is 215, which is not sufficient to produce a 100,000 unqiue keys. You could, for instance, take the product of two success calls to rand. 3. After you have inserted an appropriate number of items into the tree you should carry out a timed set of search requests using the key values that were previously inserted into the tree (that's why you stored the keys in a separate array). Note the following: a. The time can be measured by placing calls to the clock library function just before and just after the loop that carries out a number of search requests. The difference between the two values returned by clock can be divided by CLOCKS_PER_SEC to obtai ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. ## Platform c/c++ compilers in windows or linux