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 trees 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 youre 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.

____________

public class Tree> { // Node of the Binary Search Tree private class Node { E element; // element stored in this node Node left; // reference to left child Node right; // reference to right child } private Node root; // reference to this tree's root node private int size; // number of elements in this tree /** * Default constructor. Creates an empty Binary Search Tree. */ public Tree() { root = null; size = 0; } /** * Returns the number of elements in this tree. * @return size of tree */ public int size() { return size; } /** * Returns true of the given element is in this tree. * @param x element to search for * @return true if element is present */ public boolean contains(E x) { return contains(x, root); } // Recursive worker method for contains. private boolean contains(E x, Node current) { if (current == null) { return false; } else if (current.element.equals(x)) { return true; } else if (x.compareTo(current.element) < 0) { return contains(x, current.left); } else { return contains(x, current.right); } } /** * Prints the elements of this tree in-order. */ public void print() { print(root); System.out.println(); } // Recursive worker method for print. private void print(Node current) { if (current != null) { print(current.left); System.out.print(current.element + " "); print(current.right); } } /** * Adds the given element to this tree. * @param e element to add */ public void add(E e) { root = add(e, root); size++; } // Recursive worker method for add. private Node add(E e, Node current) { if(current == null) { Node n = new Node(); n.element = e; return n; } else if (e.compareTo(current.element) < 0) { current.left = add(e, current.left); } else { current.right = add(e, current.right); } return current; } /** * Removes the first occurrence of the given element from this tree. * @param x element to remove */ public void remove(E x) { Node parent = null; Node doomed = root; while(doomed != null && !doomed.element.equals(x)) { parent = doomed; doomed = x.compareTo(doomed.element) < 0 ? doomed.left : doomed.right; } if (root == doomed) { root = expunge(root); } else if (doomed != null) { if (doomed == parent.left) { parent.left = expunge(doomed); } else { parent.right = expunge(doomed); } } size--; } // Removes the specified node from the given subtree and returns the // root of the reconstructed subtree. Used by the remove method. private Node expunge(Node doomed) { if (doomed.left == null && doomed.right == null) { // Delete leaf node return null; } else if (doomed.left == null) { // Delete node with only right child return doomed.right; } else if (doomed.right == null) { // Delete node with only left child return doomed.left; } else { // Delete node with two children Node parent = doomed; Node walker = doomed.right; while (walker.left != null) { // Advance walker to replacement node parent = walker; walker = walker.left; } if (doomed == parent) { // Reconstruct subtree walker.left = parent.left; } else { parent.left = walker.right; walker.left = doomed.left; walker.right = doomed.right; } return walker; } } } ______ 

The AVL Class :

public class AVLTree> { private static final boolean OUTPUT = true; public static void main(String[] args) { int[] numbers = {89, 35, 92, 70, 57, 83, 45, 61, 88, 20}; AVLTree tree = new AVLTree(); System.out.println("Adding to AVL:"); for(int i=0; i) x).compareTo(n.element) < 0) { n.left = add(x, n.left); if (height(n.left)-height(n.right) == 2) { if(((Comparable) x).compareTo(n.left.element) < 0) { if (OUTPUT) System.out.println("Right rotation"); n = rightRotation(n); } else { if (OUTPUT) System.out.println("Left-Right rotation"); n = leftRightRotation(n); } } } else { n.right = add(x, n.right); if (height(n.right)-height(n.left) == 2) { if (((Comparable) x).compareTo(n.right.element) < 0) { if (OUTPUT) System.out.println("Right-Left rotation"); n = rightLeftRotation(n); } else { if (OUTPUT) System.out.println("Left rotation"); n = leftRotation(n); } } } n.height = Math.max(height(n.left), height(n.right)) + 1; return n; } /** * Returns the number of elements in the tree. */ public int size() { return size; } private int height(Node n) { if (n == null) { return 0; } else { return n.height; } } /** * Right rotation (rotates n's left child) */ private Node rightRotation(Node n) { Node t = n.left; n.left = t.right; t.right = n; n.height = Math.max(height(n.left), height(n.right)) + 1; t.height = Math.max(height(t.left), height(t.right)) + 1; return t; } /** * Left rotation (rotates n's right child) */ private Node leftRotation(Node n) { Node t = n.right; n.right = t.left; t.left = n; n.height = Math.max(height(n.left), height(n.right)) + 1; t.height = Math.max(height(t.left), height(t.right)) + 1; return t; } /** * Left-right rotation */ private Node leftRightRotation(Node n) { n.left = leftRotation(n.left); return rightRotation(n); } /** * Right-left rotation */ private Node rightLeftRotation(Node n) { n.right = rightRotation(n.right); return leftRotation(n); } /** * Returns this tree as a list with the elements in ascending order. * @return ordered string of elements */ public String inorder() { String s = inorder(root); return "[" + s.substring(0, s.length()-2) + "]"; } private String inorder(Node n) { if (n != null) { return inorder(n.left) + n.element + ", " + inorder(n.right); } else { return ""; } } /** * Returns a string containing the tree's elements pre-order. */ @Override public String toString() { Node walker = root; String s = "["; java.util.Stack stack = new java.util.Stack(); while (walker != null) { s += walker.element + ", "; if (walker.right != null) { stack.push(walker.right); } walker = walker.left; if (walker == null && !stack.isEmpty()) { walker = stack.pop(); } } return s.substring(0, s.length()-2) + "]"; } }