Trie Imp Algorithm
The Trie Imp Algorithm is an innovative data structure technique that is primarily used for efficiently storing and searching strings or sequences in a large dataset. It is a tree-based structure, where each node represents a single character from the sequence, and the edges connecting the nodes signify the relationship between characters. The name "trie" is derived from the word "retrieval" as it allows quick retrieval of information in a concise and organized manner. One of the key advantages of using a trie is that it provides a time complexity of O(m) for searching a string of length 'm', making it highly efficient for a wide range of applications, such as autocomplete systems, spell checkers, and IP routing.
The Trie Imp Algorithm works by inserting each character of the string one by one, starting from the root node, and traversing down the tree until the entire string has been inserted. If a character is not present along the path, a new node is created for that character. When the end of the string is reached, a special marker is added to the node to signify the completion of the string. This process is repeated for all strings in the dataset, creating a tree-like structure with shared prefixes. To search for a string within the trie, one can simply start at the root and follow the path of characters leading to the desired string. If the path terminates with the special marker, the string is considered to be present in the trie. As the trie grows, it efficiently compresses common prefixes, leading to reduced memory usage and faster search times compared to other data structures like hash tables or binary search trees.
package DataStructures.Trees;
/**
* Trie Data structure implementation without any libraries
*
* @author Dheeraj Kumar Barnwal (https://github.com/dheeraj92)
*/
import java.util.Scanner;
public class TrieImp {
public class TrieNode {
TrieNode[] child;
boolean end;
public TrieNode() {
child = new TrieNode[26];
end = false;
}
}
private final TrieNode root;
public TrieImp() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode currentNode = root;
for (int i = 0; i < word.length(); i++) {
TrieNode node = currentNode.child[word.charAt(i) - 'a'];
if (node == null) {
node = new TrieNode();
currentNode.child[word.charAt(i) - 'a'] = node;
}
currentNode = node;
}
currentNode.end = true;
}
public boolean search(String word) {
TrieNode currentNode = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = currentNode.child[ch - 'a'];
if (node == null) {
return false;
}
currentNode = node;
}
return currentNode.end;
}
public boolean delete(String word) {
TrieNode currentNode = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = currentNode.child[ch - 'a'];
if (node == null) {
return false;
}
currentNode = node;
}
if (currentNode.end == true) {
currentNode.end = false;
return true;
}
return false;
}
public static void sop(String print) {
System.out.println(print);
}
/**
* Regex to check if word contains only a-z character
*/
public static boolean isValid(String word) {
return word.matches("^[a-z]+$");
}
public static void main(String[] args) {
TrieImp obj = new TrieImp();
String word;
@SuppressWarnings("resource")
Scanner scan = new Scanner(System.in);
sop("string should contain only a-z character for all operation");
while (true) {
sop("1. Insert\n2. Search\n3. Delete\n4. Quit");
try {
int t = scan.nextInt();
switch (t) {
case 1:
word = scan.next();
if (isValid(word))
obj.insert(word);
else
sop("Invalid string: allowed only a-z");
break;
case 2:
word = scan.next();
boolean resS = false;
if (isValid(word))
resS = obj.search(word);
else
sop("Invalid string: allowed only a-z");
if (resS)
sop("word found");
else
sop("word not found");
break;
case 3:
word = scan.next();
boolean resD = false;
if (isValid(word))
resD = obj.delete(word);
else
sop("Invalid string: allowed only a-z");
if (resD) {
sop("word got deleted successfully");
} else {
sop("word not found");
}
break;
case 4:
sop("Quit successfully");
System.exit(1);
break;
default:
sop("Input int from 1-4");
break;
}
} catch (Exception e) {
String badInput = scan.next();
sop("This is bad input: " + badInput);
}
}
}
}
