A Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.
Applications
There are various applications of this special data structure such as :
- Autocomplete in mobile and web applications
- Spelling checker
- Solving word games
and many more.
Implementation
Trie is an efficient information reTrieval data structure and hence the name Trie. It is a special data structure used to store strings. It consists of nodes and edges like a tree. Each node consists of 26 children (including null and non-null values) and each node is connected to its children and parent node. These 26 children are nothing but pointers for each of the 26 letters of the English alphabet. A variable isEnd is used to mark the end of a string present in Trie. This means, combining all the alphabets from root to present character having isEnd = true makes a word, present in Trie.
Strings are stored in a top to bottom manner on the basis of their prefix in a trie. For instance:
This is an example Trie structure for strings: ["bye", "hear", "here", "hi", "hit"]
Implementing Class for each Trie node
class TrieNode {
//Children nodes
private TrieNode[] nodes;
//MAX_SIZE = Number of alphabets
private final int MAX_SIZE = 26;
//To check if it's the last node of a string in trie
private boolean isEnd;
public TrieNode[] getNodes() {
return nodes;
}
public boolean isEnd() {
return isEnd;
}
public void setEnd(boolean isEnd) {
this.isEnd = isEnd;
}
public TrieNode() {
nodes = new TrieNode[MAX_SIZE];
isEnd = false;
for (int i=0; i<MAX_SIZE; i++) {
nodes[i] = null;
}
}
}
TrieNode class: Each object of this class is representing each node in Trie data structure
Implementing Class for Trie
class Trie {
TrieNode root;
// Initializing data structure.
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
int index = word.charAt(0) - 'a';
TrieNode[] nodes = p.getNodes();
for (int i=0; i<word.length(); i++) {
index = word.charAt(i) - 'a';
if (nodes[index] == null) {
nodes[index] = new TrieNode();
}
p = nodes[index];
nodes = p.getNodes();
}
p.setEnd(true);
}
public TrieNode searchPrefix(String word) {
TrieNode p = root;
TrieNode[] nodes = p.getNodes();
for (int i=0; i<word.length(); i++) {
int index = word.charAt(i) - 'a';
if (nodes != null && nodes[index] != null) {
p = nodes[index];
nodes = p.getNodes();
} else {
return null;
}
}
return p;
}
// Returns true if the word is in the trie.
public boolean search(String word) {
TrieNode p = searchPrefix(word);
return (p != null && p.isEnd());
}
// Returns true if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = searchPrefix(prefix);
return p != null;
}
};
Main function to run Trie:
public static void main(String[] args) {
Trie obj = new Trie();
obj.insert("word");
System.out.println(obj.search("word"));
}
LeetCode problem
You could easily solve this LeetCode problem after understanding this Trie implementation:
https://leetcode.com/problems/implement-trie-prefix-tree/
Happy programming!