Lab 8: AVL and BST Height Comparison

- Study the implementation of AVLTree.java.

- Compare the implementation of BinarySearchTree.java with the one from last week lab.

- Download the following file

• Lab8.zip

In lab 7, we created a verify class that generates different set of trees for each number of nodes and find find their height average.

 In this lab you will see the height comparison between AVL and BST.

Writing a program named verify2.java that generates a number of random AVL and BST's of different sizes. Find the Minimum, Maximum, Avergae Height for each set of trees with the same number of nodes.

NOTE: You will have to implement a method height() that calculates the height of a binary tree.

Sample Output:

>java verify2

Nodes     AVL Height         BST Height
         Min Max Average     Min Max Average    Log(n)

 5        2   2    2.0        2   4     2.792   1.609

 10       3   3    3.0        3   8     4.62    2.302

 20       4   5    4.025      4   12    6.708   2.995

 40       5   6    5.263      6   15    9.073   3.688

 80       6   7    6.663      8   18    11.492  4.382