WikiGalaxy
Trie: An Introduction
What is a Trie?
A Trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set of strings. It is used to efficiently store and retrieve keys in a dataset of strings, making it a popular choice for autocomplete features.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
}
Inserting a Word in Trie
Insertion Process
To insert a word into a Trie, start from the root and insert each character of the word into a node. If a character is already present, move to the next node. Mark the end of the word by setting a flag.
class Trie {
TrieNode root;
Trie() {
root = new TrieNode();
}
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isEndOfWord = true;
}
}
Searching in a Trie
Search Operation
To search for a word in a Trie, start from the root and traverse each character. If any character is missing, the word does not exist. If you reach the end of the word and the end flag is set, the word exists.
boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isEndOfWord;
}
Deleting a Word from Trie
Deletion Process
Deleting a word from a Trie involves unmarking the end of the word. If the node has no other child nodes, it can be removed to save space.
boolean delete(String word) {
return delete(root, word, 0);
}
boolean delete(TrieNode current, String word, int index) {
if (index == word.length()) {
if (!current.isEndOfWord) {
return false;
}
current.isEndOfWord = false;
return current.children.length == 0;
}
char ch = word.charAt(index);
TrieNode node = current.children[ch - 'a'];
if (node == null) {
return false;
}
boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
if (shouldDeleteCurrentNode) {
current.children[ch - 'a'] = null;
return current.children.length == 0;
}
return false;
}
Trie for Autocomplete
Autocomplete Feature
Tries are widely used in implementing autocomplete features. By traversing the Trie, you can find all words that start with a given prefix, making it efficient for suggestions.
List autocomplete(String prefix) {
List results = new ArrayList<>();
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null) {
return results;
}
node = node.children[c - 'a'];
}
findAllWords(node, results, prefix);
return results;
}
void findAllWords(TrieNode node, List results, String prefix) {
if (node.isEndOfWord) {
results.add(prefix);
}
for (char c = 'a'; c <= 'z'; c++) {
if (node.children[c - 'a'] != null) {
findAllWords(node.children[c - 'a'], results, prefix + c);
}
}
}
