Requirements: Write a java program that performs n operations (find, insert, and

Question

Requirements: Write a java program that performs n operations (find, insert, and deleteStrings) on a BST, AVL, Splay tree and Trie and tracks the performance (hint: System.currentTimeMillis()). Your program must have at least one class called Driver2 which runs the program. Your program must have the following classes: (1) Trie. These classes should have a no argument constructor and implement the following interface. public interface BalancedTree> { public void insert(E item); public E find(E item); public void delete(E item); public void printInOrderTraversal(); public int isWellFormed();} The isWellFormed() method checks if the BST, AVL, Splay tree, and Trie is follows the appropriate rules (0 for true and 1 for false).

Explanation / Answer

class Node{ //class for each node of the AVL Tree
Node lft,rht; //lft and rht children nodes
String data; //the data stored in the tree
int hgt; //hgt of the sub-tree
  
Node(){ //default constructor
lft=rht=null;
data=null;
hgt=0;
}
Node(String str){ //constructor
lft=rht=null;
data=str;
hgt=0;
}
}
public class AVL implements BalancedTree{
private Node root;
  
AVL(){ //default constructor
root=null;
}
boolean isEmpty(){ //is tree empty?
return root==null;
}
  
private int gethgt(Node n){ //get the hgt of the node
if(n==null)
return -1;
else
return n.hgt;
}
  
public void insert(String str){ //insert data into the tree
root=insert(str,root); //call the overloaded method insert that takes 2 params String and Node returns a Node(defined below)
}
  
private Node insert(String str,Node n){
if(n==null) //if the node is empty, create a new node
n=new Node();
else if(str.compareTo(n.data)<0){ //if str<n.data
n.lft=insert(str,n.lft); //insert new the lft child
if(gethgt(n.lft)-gethgt(n.rht)==2) //if sub-tree is unbalanced
if(str.compareTo(n.lft.data)<0) //if new data is < data of the lft child
n=rotateLft(n); //lft rotation
else
n=rotateRht(n); //rht rotation
}
else if(str.compareTo(n.data)>0){ //if str>n.data
n.rht=insert(str,n.rht); //insert new the rht child
if(gethgt(n.rht)-gethgt(n.lft)==2) //if sub-tree is unbalanced
if(str.compareTo(n.rht.data)>0) //if new data is > data of the rht child
n=rotateRht(n); //rht rotation
else
n=rotateLft(n); //lft rotation
}
//in case str==n.data, the data is duplicate and must not be inserted into the tree
  
//calculate the hgt of the new node
// n.hgt=max(gethgt(n.lft),gethgt(n.rht))+1;
if(gethgt(n.lft)>gethgt(n.rht))
n.hgt=n.lft.hgt+1;
else
n.hgt=n.rht.hgt+1;
//return new node
return n;
}
  
private Node rotateLft(Node n1){
Node n2=n1.lft;
  
n1.lft=n2.rht;
n2.rht=n1;
  
if(n1.lft.hgt>n1.rht.hgt)
n1.hgt=n1.lft.hgt+1;
else
n1.hgt=n1.rht.hgt+1;
  
if(n2.lft.hgt>n2.rht.hgt)
n2.hgt=n2.lft.hgt+1;
else
n2.hgt=n2.rht.hgt+1;

return n2;
}
  
private Node rotateRht(Node n1){
Node n2=n1.rht;
  
n1.rht=n2.lft;
n2.lft=n1;
  
if(n1.lft.hgt>n1.rht.hgt)
n1.hgt=n1.lft.hgt+1;
else
n1.hgt=n1.rht.hgt+1;
  
if(n2.lft.hgt>n2.rht.hgt)
n2.hgt=n2.lft.hgt+1;
else
n2.hgt=n2.rht.hgt+1;

return n2;
}
  
//double rotations
private Node LftRhtRotation(Node n3){
n3.lft=rotateRht(n3.lft);
return rotateLft(n3);
}
private Node RhtLftRotation(Node n3){
n3.rht=rotateLft(n3.rht);
return rotateRht(n3);
}
  
public String find(String item){
return find(root,item); //call overloaded find() defined below
}
private String find(Node n, String str){
long t_time=System.currTimeMillis(); //curr time
boolean foundFlag=false; //set to true if string found in the tree
String retStr="Not Found"; //string to be returned
while((n!=null) && !foundFlag){
String temp=n.data;
if(str.compareTo(temp)<0)
n=n.lft;
else if(str.compareTo(temp)>0)
n=n.rht;
else{
foundFlag=true;
break;
}
retStr=find(n,str);
}
t_time-=System.currTimeMillis();
System.out.println("Time taken to search is "+t_time+" milliseconds");
return retStr;
}
public void printInORderTraversal(){
inOrder(root);
}
private void inOrder(Node n){
if(n!=null){
inOrder(n.lft);
System.out.print(n.data + " ");
inOrder(n.rht);
}
}
public int isWellFormed(){
return isWellFormed(root);
}
private int isWellFormed(Node n){
int valRet; //return value
if(n!=null){
isWellFormed(n.lft);
if(n.hgt>1)
valRet= 0;
else
valRet= 1;
isWellFormed(n.rht);
}
return 1;
}
}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.