Modify the main method so that it does the following: Creates an ArrayList of N
ID: 3836553 • Letter: M
Question
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?
Why does one take so much longer than the other?
The Classes:
// AVL Tree Class:
_______________________
Tree Class:
______________
N
AVL height
BST height
1,000
10,000
100,000
250,000
500,000
Explanation / Answer
I have added height() methods in Tree class:
public class Tree<E extends Comparable<E>> {
// 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;
}
public int height() {
return height(root);
}
private int height(Node node){
if(node == null)
return 0;
int lh = height(node.left);
int rh = height(node.right);
if(lh > rh)
return lh+1;
else
return rh + 1;
}
/**
* 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;
}
}
}
######################
import java.util.ArrayList;
import java.util.Random;
public class TreeHeightCompare {
public static ArrayList<Integer> getRandomList(int n){
ArrayList<Integer> list = new ArrayList<>();
Random random = new Random();
for(int i=1; i<=n; i++)
list.add(random.nextInt(100));
return list;
}
public static void main(String[] args) {
Tree<Integer> bst = new Tree<>();
AVLTree<Integer> avl = new AVLTree<>();
ArrayList<Integer> list = null;
System.out.println("N AVL height BST height");
int N = 1000;
list = getRandomList(N);
//System.out.println("Adding "+N+" elements in BST");
for(int i=0; i<list.size(); i++)
bst.add(list.get(i));
//System.out.println("Adding "+N+" elements in AVL");
for(int i=0; i<list.size(); i++)
avl.add(list.get(i));
System.out.println(N+" "+avl.height()+" "+bst.height());
N = 10000;
list = getRandomList(N);
//System.out.println("Adding "+N+" elements in BST");
for(int i=0; i<list.size(); i++)
bst.add(list.get(i));
//System.out.println("Adding "+N+" elements in AVL");
for(int i=0; i<list.size(); i++)
avl.add(list.get(i));
System.out.println(N+" "+avl.height()+" "+bst.height());
N = 100000;
list = getRandomList(N);
//System.out.println("Adding "+N+" elements in BST");
for(int i=0; i<list.size(); i++)
bst.add(list.get(i));
//System.out.println("Adding "+N+" elements in AVL");
for(int i=0; i<list.size(); i++)
avl.add(list.get(i));
System.out.println(N+" "+avl.height()+" "+bst.height());
N = 250000;
list = getRandomList(N);
//System.out.println("Adding "+N+" elements in BST");
for(int i=0; i<list.size(); i++)
bst.add(list.get(i));
//System.out.println("Adding "+N+" elements in AVL");
for(int i=0; i<list.size(); i++)
avl.add(list.get(i));
System.out.println(N+" "+avl.height()+" "+bst.height());
N = 500000;
list = getRandomList(N);
//System.out.println("Adding "+N+" elements in BST");
long start = System.currentTimeMillis();
for(int i=0; i<list.size(); i++)
bst.add(list.get(i));
long end = System.currentTimeMillis();
long bstInsertion = (end-start);
//System.out.println("Adding "+N+" elements in AVL");
start = System.currentTimeMillis();
for(int i=0; i<list.size(); i++)
avl.add(list.get(i));
end = System.currentTimeMillis();
long avlInsertion = (end-start);
System.out.println(N+" "+avl.height()+" "+bst.height());
System.out.println();
System.out.println("time taken by BST to insert 500000: "+bstInsertion);
System.out.println("time taken by AVL to insert 500000: "+avlInsertion);
}
}
/*
N AVL height BST height
1000 12 30
10000 15 142
100000 19 1199
250000 20 3775
500000 22 8827
time taken by BST to insert 500000: 126004
time taken by AVL to insert 500000: 200
*/
Why does one take so much longer than the other?
In AVL tree, it maintains height difference 1 between right and left subtree, so there will be very less level as compare to BST. So it takes O(logN) time to insert in AVL but it takes O(h) time to insert in BST on an average. So BST will take more time
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.