make sure the program is generic and has the following requirements. Write a jav
ID: 3836552 • Letter: M
Question
make sure the program is generic and has the following requirements.
Write a java program that performs n operations (find, insert, and delete Strings) on a Trie tree and tracks the performance using System.currentTimeMillis(). The program must have at least one class called Driver2 which runs the program. The program must have the following class: Trie.java and should not have an 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
PROGRAM:
import java.util.*;
class TrieNode {
char content;
boolean isEnd;
int count;
LinkedList childList;
/* Constructor */
public TrieNode(char c) {
childList=new LinkedList();
isEnd=false;
content=c;
count=0;
}
public TrieNode subNode(char c) {
if(childList !=null) for (TrieNode eachChild:childList)
if(eachChild.content==c)
return eachChild;
return null;
}}
class Trie {
private TrieNode root;
/* Constructor */
public Trie() {
root=new TrieNode(' ');
}
/* Function to insert word */
public void insert(String word) {
if(search(word)==true)
return;
TrieNode current=root;
for(char ch:word.toCharArray() )
{
TrieNode child=current.subNode(ch);
if(child!=null)
current=child;
else
{
current.childList.add(new TrieNode(ch));
current=current.subNode(ch);
}
current.count++;
}
current.isEnd=true;
}
/* Function to search for word */
public boolean search(String word) {
TrieNode current=root;
for(char ch:word.toCharArray() )
{
if(current.subNode(ch)==null)
return false;
else
current=current.subNode(ch);
}
if(current.isEnd==true)
return true;
return false;
}
/* Function to remove a word */
public void remove(String word) {
if(search(word)==false)
{
System.out.println(word +"does not exist in trie ");
return;
}
TrieNode current=root;
for(char ch : word.toCharArray())
{
TrieNode child=current.subNode(ch);
if(child.count==1)
{
current.childList.remove(child);
return;
}
else
{
child.count--;
current=child;
}
}
current.isEnd=false;
}
}
/* Class Trie Test */
public class TrieTest {
public static void main(String[ ] args) {
Scanner scan=new Scanner(System.in);
/* Creating object of AATree */
Trie t=new Trie();
System.out.println("TrieTest ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" Trie Operations ");
System.out.println("1.insert");
System.out.println("2.delete");
System.out.println("3.search");
int choice=scan.nextInt;
switch(choice)
{
case 1 :
System.out.println("Enter string element to insert");
t.insert(scan.next() );
break;
case 2 :
System.out.println("Enter string element to delete");
try
{
t.delete(scan.next() );
}
catch(Exception e)
{
System.out.println(e.getMessage()+ "not found");
}
break;
case 3 :
System.out.println("Enter string element to search");
System.out.println("Search result:"+ t.search(scan.next() ));
break;
default:
System.out.println("wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch=scan.next().charAt(0);
}
while(ch =='Y' || ch=='y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.