WikiGalaxy
Trie Data Structure
Introduction to Trie:
A Trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set of strings, where the keys are usually strings. It is used for efficient retrieval of a key in a dataset of strings. The main idea of a Trie is to store strings in a way that common prefixes are only stored once.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++)
children[i] = null;
}
}
class Trie {
TrieNode root;
Trie() {
root = new TrieNode();
}
void insert(String key) {
int level;
int length = key.length();
int index;
TrieNode pCrawl = root;
for (level = 0; level < length; level++) {
index = key.charAt(level) - 'a';
if (pCrawl.children[index] == null)
pCrawl.children[index] = new TrieNode();
pCrawl = pCrawl.children[index];
}
pCrawl.isEndOfWord = true;
}
}
Insert Operation:
The insert operation in a Trie involves traversing the tree and creating nodes if they do not exist. Each character of the input string is stored at a node in the Trie.
Searching in a Trie
Search Operation:
Searching for a key in a Trie involves traversing the nodes for each character of the key. If we reach the end of the key and the isEndOfWord flag is true, the key exists in the Trie.
boolean search(String key) {
int level;
int length = key.length();
int index;
TrieNode pCrawl = root;
for (level = 0; level < length; level++) {
index = key.charAt(level) - 'a';
if (pCrawl.children[index] == null)
return false;
pCrawl = pCrawl.children[index];
}
return (pCrawl != null && pCrawl.isEndOfWord);
}
Efficiency:
The search operation is efficient with a time complexity of O(L), where L is the length of the key being searched.
Deleting from a Trie
Delete Operation:
Deleting a key from a Trie involves unmarking the isEndOfWord flag of the last node of the key. If a node does not have any children, it can be removed to save space.
boolean delete(String key) {
return deleteHelper(root, key, 0);
}
boolean deleteHelper(TrieNode current, String key, int depth) {
if (current == null)
return false;
if (depth == key.length()) {
if (current.isEndOfWord)
current.isEndOfWord = false;
return current.children.length == 0;
}
int index = key.charAt(depth) - 'a';
if (deleteHelper(current.children[index], key, depth + 1)) {
current.children[index] = null;
return !current.isEndOfWord && current.children.length == 0;
}
return false;
}
Space Optimization:
By deleting unnecessary nodes, the Trie can be optimized for space, ensuring that no redundant nodes are stored.
Applications of Trie
Autocomplete Systems:
Tries are extensively used in autocomplete systems where they help in suggesting words based on the prefix typed by the user.
// Function to suggest words based on a given prefix
void autoComplete(TrieNode current, String prefix) {
if (current.isEndOfWord)
System.out.println(prefix);
for (char c = 'a'; c <= 'z'; c++) {
TrieNode next = current.children[c - 'a'];
if (next != null)
autoComplete(next, prefix + c);
}
}
Efficiency in Autocomplete:
The time complexity for finding all words with a given prefix is O(P + N), where P is the length of the prefix and N is the number of matching words.
Advantages and Limitations
Advantages:
Tries offer fast retrieval and insertion of keys, making them ideal for applications requiring quick lookups.
Limitations:
The main disadvantage is the space consumption, as tries can require a lot of memory, especially when storing a large set of strings.
// Example to demonstrate space usage
int calculateMemoryUsage(TrieNode node) {
if (node == null) return 0;
int size = 1; // for the node itself
for (TrieNode child : node.children)
size += calculateMemoryUsage(child);
return size;
}
Memory Usage Analysis:
The memory usage of a Trie can be significant, especially if the Trie is not balanced or optimized for the specific dataset it is handling.
