I Need this assignment to be in Java language Problem 1: Tree Height Add a metho
ID: 3717216 • Letter: I
Question
I Need this assignment to be in Java language
Problem 1: Tree Height
Add a method to the Tree class that returns the height of the tree. The height of a tree is the number of links between the root and the deepest leaf.
Problem 2: The AVL Tree
Currently, the main method creates an AVL tree out of a fixed set of integers. The AVL tree’s add method is designed to print the name of the rotation each time the tree is re-balanced. Before running the program, draw a picture of the AVL tree that will be constructed from the set of integers. Identify the rotations you use whenever you have to balance the tree. When you’re done, run the program to see if it uses the same rotations you did. Print the AVL tree. This will print the integers in pre-order. Does the pre-order traversal of the AVL tree match the tree you drew?
You can experiment with the program, having it create trees of random integers to see if you can predict which rotations will be applied.
Problem 3: Modify the main method so that it does the following:
Creates an ArrayList of N random integers that are less than 100.
Traverses the ArrayList and adds all of the integers to an AVL tree.
Traverses the ArrayList a second time and adds all of the integers to a regular binary search tree.
Prints the height of the AVL tree.
Prints the height of the binary search tree.
The two ArrayList traversals must be in separate loops for this experiment. Add print statements before each loop to identify what the program is doing.
Run the program with the following values of N and fill in the table below. Be sure to set the OUTPUT field in the AVL class to false to avoid printing all the rotations.
N
AVL height
BST height
1,000
10,000
100,000
250,000
500,000
The AVL add method seems to do a lot more work than the BST add method. It must compute the height of each node, detect when the tree becomes unbalanced, figure out which rotation to apply and then apply the rotation. This seems to suggest that it should take longer to add elements to an AVL tree than it takes to add elements to a regular binary search tree. Is this, in fact, the case? Answer the following questions:
How long does it take to add 500,000 integers to an AVL tree?
How long does it take to add 500,000 integers to a binary search tree?
Does one take noticeably longer than the other? If so, why?
------------------------------------------------------------------------
--------------------------------------------------------------------
N
AVL height
BST height
1,000
10,000
100,000
250,000
500,000
Explanation / Answer
As, Per the chegg policy, please post one question in a post.
I have answered Q1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.