A trie or prefix tree is a data structure based on a tree-like data structure. It is used for efficient storage and retrieval of the strings. Thus, the name “trie” is derived from the word “retrieval”, pronounced as “try”.
Every character of the string is stored as the node of the tree, the path from root to leaf representing a string.
For example, the representation of apple in Trie would be :
similarly the representation of “apple “, “apply” , “ant “ and “aunt “ would be:
NODE IN TRIE
Every node of the trie consists of an array of character representing all the alphabets, and a boolean variable which is used to represent the termination of the word.
struct Node{
Node* child[26];
bool isterm;
}Insertion in trie
Insertion in trie works by checking if there is a node available with the required character. If new node is required then we create a new Node.
Insertion(string s)
Node* node = root;
for(auto it: s){
if(p->child[it-'a']==NULL){
p->child[it-'a'] = new Node();
p = p->child[it-'a'];
p->isterm = true;Search in a Trie
Using this function we can check if the given string is present in the trie or not. We check the string character-by-character, if a character is not present in the trie, return false. In the end, check if the word is terminated. If it is not terminated, return false.
Searching using prefix
bool startsWith(string prefix) {
Node* p =root;
for(auto it:prefix){
if(p->a[it-'a']==NULL) return false;
p = p->a[it-'a'];
}
return true;
}Implementation of trie
struct Node{
Node* a[26];
bool isterm;
};
class Trie {
public:
Node* root ;
bool endofword ;
Trie() {
root= new Node();
}
//this is used to insert the word in a trie
void insert(string word){
Node *p = root;
for(auto it :word){
if(p->a[it-'a']==NULL){
p->a[it-'a'] = new Node();
}
p = p->a[it-'a'];
}
p->isterm =true;
}
//used to check for the searching a particular word
bool search(string word) {
Node *p = root;
for(auto it:word){
if(p->a[it-'a']==NULL) return false;
p= p->a[it-'a'];
}
return p->isterm;
}
// start with function is used to check if there are string with the given prefix
bool startsWith(string prefix) {
Node* p =root;
for(auto it:prefix){
if(p->a[it-'a']==NULL) return false;
p = p->a[it-'a'];
}
return true;
}
};Practice Question For tries :
https://leetcode.com/problems/implement-trie-prefix-tree/description/
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/
https://leetcode.com/problems/design-add-and-search-words-data-structure/description/