Problem 1: Tree Height Add a method to the Tree class that returns the height of
ID: 3835875 • Letter: P
Question
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 maximum number of nodes between the root and a 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:
1. How long does it take to add 500,000 integers to an AVL tree?
2. How long does it take to add 500,000 integers to a binary search tree?
3. Why does one take so much longer than the other?
__________________
I am studying for my final and I have this questions about old material ...
Can you guys help me out with this Tree. I am new to this material.
thnx.
please help me with answering the questions above.
____________
The AVL Class :
Explanation / Answer
Use this code to find the height of the tree. The function takes a parameter which is the root of the tree.
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
int lHeight = height(node->left);
int rHeight = height(node->right);
if (lHeight > rHeight)
return(lHeight+1);
else return(rHeight+1);
}
}
Thanks
Nikhil Jain