and the following methods to the BinarySearchTree class:
numOccur(value)
Returns the number of times value
appears in the tree.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.
Be sure to test your methods thoroughly before continuing.
numBelow(value)
Returns the number of tree entries that are smaller than value
.numAbove(value)
Returns the number of tree entries that are bigger than value
.avgCost()
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. For example,
number of values (N) | ⌈log_{2}(N+1)⌉ | average cost | average height |
---|---|---|---|
N = 1,000 | |||
N = 2,000 | |||
N = 4,000 | |||
N = 8,000 | |||
N = 16,000 |