It has been proven that the average search cost for an arbitrary item in an arbitrary binary
search tree of N items is O(log N). You are to verify this result experimentally.
Write a program that prompts the user for the number
of items to be stored (N) and the number of trees to generate (T). Then, it should repeatedly
(T times) store N random
numbers in a binary search tree and compute the average cost of searching that tree. Recall
average cost of a search = (weight of the tree / number of nodes in tree).
Your program should display the average of these costs over all of the constructed
trees. In addition, it should display the average height of the trees. For example,
Number of values to be stored: 1000
Number of trees to generate: 100
Generating 100 trees with 1000 random values:
average cost = 11.9146
average height = 21.76