and the following method to the BinarySearchTree class:
height()
Returns the height of the tree, i.e., the length of the longest path from the root to a leaf. weight()
Returns the weight of the tree, i.e., the sum of all the node depths.
Note: all three methods should return 0 if applied to an empty tree. Be sure to test your methods thoroughly before continuing.
avgSearchCost()
Returns the average cost of a search in the tree, i.e., weight/size.
Your program should display the average of these heights and costs over all of the constructed trees, as well as the minimum possible tree height (⌈log_{2}(N+1)⌉). For example,
number of values (N) | min possible height | average tree height | average search cost |
---|---|---|---|
N = 1,000 | |||
N = 2,000 | |||
N = 4,000 | |||
N = 8,000 | |||
N = 16,000 | |||
N = 32,000 |