Question

Write a program that does the following. *Java Code*

• Create an instance of the Hashtable class from the Java API

• Make the initial table size of the hash table 1000 and the load factor 0.75 (which has been shown experimentally to be optimal).

• Create an instance of the AVLtree class attached to this homework.

• Measure the running time of adding various numbers of entries (as required by the table below) to the hash table and the AVL tree.

• For each of those cases, measure the running time of searching for a key that is not in the hash table and do the same for the AVL tree.

Fill in the following charts. Adjust the values of n as needed according to your platform to obtain at least 4 measurements.

construction time n = 10^2 n = 10^3 n = 10^4 n = 10^5 n = 10^6

Hash table

Tree

search time n = 10^2 n = 10^3 n = 10^4 n = 10^5 n = 10^6

Hash table

Tree

How do these measurements compare with your conjecture in parts 1 and 2? If the results differ from your conjecture, investigate the reason by looking carefully at the code of Hashtable and AVLtree provided and explain what might have happened.

Answer 1

import java.util.Scanner;

/ Class AVLNode /
class AVLNode
{
AVLNode left, right;
int data;
int height;

/ Constructor /
public AVLNode()
{
left = null;
right = null;
data = 0;
height = 0;
}
/ Constructor /
public AVLNode(int n)
{
left = null;
right = null;
data = n;
height = 0;
}
}

/ Class AVLTree /
class AVLTree
{
private AVLNode root;

/ Constructor /
public AVLTree()
{
root = null;
}
/ Function to check if tree is empty /
public boolean isEmpty()
{
return root == null;
}
/ Make the tree logically empty /
public void makeEmpty()
{
root = null;
}
/ Function to insert data /
public void insert(int data)
{
root = insert(data, root);
}
/ Function to get height of node /
private int height(AVLNode t )
{
return t == null ? -1 : t.height;
}
/ Function to max of left/right node /
private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
/ Function to insert data recursively /
private AVLNode insert(int x, AVLNode t)
{
if (t == null)
t = new AVLNode(x);
else if (x < t.data)
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x < t.left.data )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x > t.data )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x > t.right.data)
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/ Rotate binary tree node with left child /
private AVLNode rotateWithLeftChild(AVLNode k2)
{
AVLNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}

/ Rotate binary tree node with right child /
private AVLNode rotateWithRightChild(AVLNode k1)
{
AVLNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
with its right child; then node k3 with new left child /
private AVLNode doubleWithLeftChild(AVLNode k3)
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: first right child
with its left child; then node k1 with new right child /
private AVLNode doubleWithRightChild(AVLNode k1)
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
/ Functions to count number of nodes /
public int countNodes()
{
return countNodes(root);
}
private int countNodes(AVLNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
/ Functions to search for an element /
public boolean search(int val)
{
return search(root, val);
}
private boolean search(AVLNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.data;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/ Function for inorder traversal /
public void inorder()
{
inorder(root);
}
private void inorder(AVLNode r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}
/ Function for preorder traversal /
public void preorder()
{
preorder(root);
}
private void preorder(AVLNode r)
{
if (r != null)
{
System.out.print(r.data +" ");
preorder(r.left);
preorder(r.right);
}
}
/ Function for postorder traversal /
public void postorder()
{
postorder(root);
}
private void postorder(AVLNode r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data +" ");
}
}
}

/ Class AVL Tree Test /
public class AVLTreeTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/ Creating object of AVLTree /
AVLTree avlt = new AVLTree();

System.out.println("AVLTree Tree Test\n");
char ch;
/ Perform tree operations /
do
{
System.out.println("\nAVLTree Operations\n");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");

int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
avlt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ avlt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ avlt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ avlt.isEmpty());
break;
case 5 :
System.out.println("\nTree Cleared");
avlt.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/ Display tree /
System.out.print("\nPost order : ");
avlt.postorder();
System.out.print("\nPre order : ");
avlt.preorder();
System.out.print("\nIn order : ");
avlt.inorder();

System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
advertisements

AVLTree Tree Test

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
4
Empty status = true

Post order :
Pre order :
In order :
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
10

Post order : 10
Pre order : 10
In order : 10
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
9

Post order : 9 10
Pre order : 10 9
In order : 9 10
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
8

Post order : 8 10 9
Pre order : 9 8 10
In order : 8 9 10
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
7

Post order : 7 8 10 9
Pre order : 9 8 7 10
In order : 7 8 9 10
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
6

Post order : 6 8 7 10 9
Pre order : 9 7 6 8 10
In order : 6 7 8 9 10
Do you want to continue (Type y or n)

y

AVLTree Operations

1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
5

Post order : 5 6 8 10 9 7
P