Write a java program that performs n operations (find, insert, and delete String

Question

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

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("Trie Test "); 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.remove( 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

• Browse (All)
• Browse W
• Subjects

---

---

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