Lab 7: BST Average Height
In this lab you will test empirically whether this important belief about binary search trees is accurate:
"the height of a random binary search tree of n records is Theta(log n)".
By random, I mean a BST created from a series of random numbers included in some random order.
Verify this result by writing a program named verify.java that generates a number of random binary search trees of different sizes and averages the height of all of the constructed trees for every size. The behavior of this variable height should be similar to log n. Show that.
NOTE: You will have to implement a method height() that calculates the height of a BST.
> java verify
--------------------------------------------------------------------------------
Number of Tries = 10
Number of Nodes : 5 Average Height =
2.8
Number of Nodes : 10 Average Height = 4.4
Number of Nodes : 20 Average Height = 6.1
Number of Nodes : 40 Average Height = 9.5
Number of Nodes : 80 Average Height = 11.2
Number of Nodes : 160 Average Height = 13.3
Number of Nodes : 320 Average Height = 17.4
Number of Nodes : 640 Average Height = 19.4
--------------------------------------------------------------------------------