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

Question

Requirements: Write ajava program that performs n operations (find, insert, and delete Strings) on a BST, AVL, Splay tree and Trie and tracks the performance (hint: System current TimeMillis0) Your program must have at least one class called Driver2 which runs the program. Your program must have the following classes: (1) BST java, (2) AVLjava, (3) Splayjava, and (4) 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 isWell Formed The isWellFormed0 method checks if the BST, AVL, Splay tree, and Trie is follows the appropriate rules (0 for true and 1 for false).

Explanation / Answer

I couldn't complete the delete() method. But you should be able to do it referencing the balancing and insert() methods. Do let me know if you need help with it.

class Node{ //class for each node of the AVL Tree
Node left,right; //left and right children nodes
String data; //the data stored in the tree
int height; //height of the sub-tree
  
Node(){ //default constructor
left=right=null;
data=null;
height=0;
}
Node(String str){ //constructor
left=right=null;
data=str;
height=0;
}
}
public class AVL implements BalancedTree{
private Node root;
  
AVL(){ //default constructor
root=null;
}
boolean isEmpty(){ //is tree empty?
return root==null;
}
  
private int getheight(Node n){ //get the height of the node
if(n==null)
return -1;
else
return n.height;
}
  
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.left=insert(str,n.left); //insert new the left child
if(getheight(n.left)-getheight(n.right)==2) //if sub-tree is unbalanced
if(str.compareTo(n.left.data)<0) //if new data is < data of the left child
n=rotateLeft(n); //left rotation
else
n=rotateRight(n); //right rotation
}
else if(str.compareTo(n.data)>0){ //if str>n.data
n.right=insert(str,n.right); //insert new the right child
if(getheight(n.right)-getheight(n.left)==2) //if sub-tree is unbalanced
if(str.compareTo(n.right.data)>0) //if new data is > data of the right child
n=rotateRight(n); //right rotation
else
n=rotateLeft(n); //left rotation
}
//in case str==n.data, the data is duplicate and must not be inserted into the tree
  
//calculate the height of the new node
// n.height=max(getheight(n.left),getheight(n.right))+1;
if(getheight(n.left)>getheight(n.right))
n.height=n.left.height+1;
else
n.height=n.right.height+1;
//return new node
return n;
}
  
private Node rotateLeft(Node n1){
Node n2=n1.left;
  
n1.left=n2.right;
n2.right=n1;
  
if(n1.left.height>n1.right.height)
n1.height=n1.left.height+1;
else
n1.height=n1.right.height+1;
  
if(n2.left.height>n2.right.height)
n2.height=n2.left.height+1;
else
n2.height=n2.right.height+1;

return n2;
}
  
private Node rotateRight(Node n1){
Node n2=n1.right;
  
n1.right=n2.left;
n2.left=n1;
  
if(n1.left.height>n1.right.height)
n1.height=n1.left.height+1;
else
n1.height=n1.right.height+1;
  
if(n2.left.height>n2.right.height)
n2.height=n2.left.height+1;
else
n2.height=n2.right.height+1;

return n2;
}
  
//double rotations
private Node LeftRightRotation(Node n3){
n3.left=rotateRight(n3.left);
return rotateLeft(n3);
}
private Node RightLeftRotation(Node n3){
n3.right=rotateLeft(n3.right);
return rotateRight(n3);
}
  
public String find(String item){
return find(root,item); //call overloaded find() defined below
}
private String find(Node n, String str){
long timetaken=System.currentTimeMillis(); //current 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.left;
else if(str.compareTo(temp)>0)
n=n.right;
else{
foundFlag=true;
break;
}
retStr=find(n,str);
}
timetaken-=System.currentTimeMillis();
System.out.println("Time taken to search is "+timetaken+" milliseconds");
return retStr;
}
public void printInORderTraversal(){
inOrder(root);
}
private void inOrder(Node n){
if(n!=null){
inOrder(n.left);
System.out.print(n.data + " ");
inOrder(n.right);
}
}
public int isWellFormed(){
return isWellFormed(root);
}
private int isWellFormed(Node n){
int retval; //return value
if(n!=null){
isWellFormed(n.left);
if(n.height>1)
retval= 0;
else
retval= 1;
isWellFormed(n.right);
}
return 1;
}
}

Hope this helps!

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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