A trie is a type of a multi-way search tree, which is fundamentally used to retrieve specific keys from a string or a set of strings. It stores the data in an ordered efficient way since it uses pointers to every letter within the alphabet.
The trie data structure works based on the common prefixes of strings. The root node can have any number of nodes considering the amount of strings present in the set. The root of a trie does not contain any value except the pointers to its child nodes.
There are three types of trie data structures −
- Standard Tries
- Compressed Tries
- Suffix Tries
The real-world applications of trie include − autocorrect, text prediction, sentiment analysis and data sciences.
Basic Operations in Tries
The trie data structures also perform the same operations that tree data structures perform. They are −
- Insertion
- Deletion
- Search
Insertion operation
The insertion operation in a trie is a simple approach. The root in a trie does not hold any value and the insertion starts from the immediate child nodes of the root, which act like a key to their child nodes. However, we observe that each node in a trie represents a singlecharacter in the input string. Hence the characters are added into the tries one by one while the links in the trie act as pointers to the next level nodes.
Example
Following are the implementations of this operation in various programming languages −
#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26structTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};structTrie{structTrieNode* root;};structTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
node->children[i]=NULL;}return node;}voidinsert(structTrie* trie,constchar* key){structTrieNode* curr = trie->root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(curr->children[index]==NULL){
curr->children[index]=createNode();}
curr = curr->children[index];}
curr->isEndOfWord =1;}voidprintWords(structTrieNode* node,char* prefix){if(node->isEndOfWord){printf("%s\n", prefix);}for(int i =0; i < ALPHABET_SIZE; i++){if(node->children[i]!=NULL){char* newPrefix =(char*)malloc(strlen(prefix)+2);strcpy(newPrefix, prefix);
newPrefix[strlen(prefix)]='A'+ i;
newPrefix[strlen(prefix)+1]='\0';printWords(node->children[i], newPrefix);free(newPrefix);}}}intmain(){structTrie car;
car.root =createNode();insert(&car,"lamborghini");insert(&car,"mercedes-Benz");insert(&car,"land Rover");insert(&car,"maruti Suzuki");printf("Trie elements are:\n");printWords(car.root,"");return0;}
Output
Trie elements are: LAMBORGHINI LANDNOVER MARUTIOUZUKI MERCEZENZ
Deletion operation
The deletion operation in a trie is performed using the bottom-up approach. The element is searched for in a trie and deleted, if found. However, there are some special scenarios that need to be kept in mind while performing the deletion operation.
Case 1 − The key is unique − in this case, the entire key path is deleted from the node. (Unique key suggests that there is no other path that branches out from one path).
Case 2 − The key is not unique − the leaf nodes are updated. For example, if the key to be deleted is see but it is a prefix of another key seethe; we delete the see and change the Boolean values of t, h and e as false.
Case 3 − The key to be deleted already has a prefix − the values until the prefix are deleted and the prefix remains in the tree. For example, if the key to be deleted is heart but there is another key present he; so we delete a, r, and t until only he remains.
Example
Following are the implementations of this operation in various programming languages −
//C code for Deletion Operation of tries Algorithm#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <string.h>//Define size 26#define ALPHABET_SIZE 26structTrieNode{structTrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;};structTrie{structTrieNode* root;};structTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
node->isEndOfWord = false;for(int i =0; i < ALPHABET_SIZE; i++){
node->children[i]=NULL;}return node;}voidinsert(structTrie* trie,constchar* key){structTrieNode* curr = trie->root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(curr->children[index]==NULL){
curr->children[index]=createNode();}
curr = curr->children[index];}
curr->isEndOfWord =1;}
bool search(structTrieNode* root,char* word){structTrieNode* curr = root;for(int i =0; word[i]!='\0'; i++){int index = word[i]-'a';if(curr->children[index]==NULL){return false;}
curr = curr->children[index];}return(curr !=NULL&& curr->isEndOfWord);}
bool startsWith(structTrieNode* root,char* prefix){structTrieNode* curr = root;for(int i =0; prefix[i]!='\0'; i++){int index = prefix[i]-'a';if(curr->children[index]==NULL){return false;}
curr = curr->children[index];}return true;}
bool deleteWord(structTrieNode* root,char* word){structTrieNode* curr = root;structTrieNode* parent =NULL;int index;for(int i =0; word[i]!='\0'; i++){
index = word[i]-'a';if(curr->children[index]==NULL){return false;// Word does not exist in the Trie}
parent = curr;
curr = curr->children[index];}if(!curr->isEndOfWord){return false;// Word does not exist in the Trie}
curr->isEndOfWord = false;// Mark as deletedif(parent !=NULL){
parent->children[index]=NULL;// Remove the child node}return true;}voidprintWords(structTrieNode* node,char* prefix){if(node->isEndOfWord){printf("%s\n", prefix);}for(int i =0; i < ALPHABET_SIZE; i++){if(node->children[i]!=NULL){char* newPrefix =(char*)malloc(strlen(prefix)+2);strcpy(newPrefix, prefix);
newPrefix[strlen(prefix)]='a'+ i;
newPrefix[strlen(prefix)+1]='\0';printWords(node->children[i], newPrefix);free(newPrefix);}}}intmain(){structTrie car;
car.root =createNode();insert(&car,"lamborghini");insert(&car,"mercedes-Benz");insert(&car,"landrover");insert(&car,"maruti Suzuki");//Before Deletionprintf("Tries elements before deletion: \n");printWords(car.root,"");//Deleting the elementschar* s1 ="lamborghini";char* s2 ="landrover";printf("Elements to be deleted are: %s and %s", s1, s2);deleteWord(car.root, s1);deleteWord(car.root, s2);//After Deletionprintf("\nTries elements before deletion: \n");printWords(car.root,"");}
Output
Tries elements before deletion: lamborghini landrover marutiouzuki mercezenz Elements to be deleted are: lamborghini and landrover Tries elements before deletion: marutiouzuki mercezenz
Search operation
Searching in a trie is a rather straightforward approach. We can only move down the levels of trie based on the key node (the nodes where insertion operation starts at). Searching is done until the end of the path is reached. If the element is found, search is successful; otherwise, search is prompted unsuccessful.
Example
Following are the implementations of this operation in various programming languages −
//C program for search operation of tries algorithm#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define ALPHABET_SIZE 26structTrieNode{structTrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;};structTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
node->isEndOfWord = false;for(int i =0; i < ALPHABET_SIZE; i++){
node->children[i]=NULL;}return node;}voidinsert(structTrieNode* root,char* word){structTrieNode* curr = root;for(int i =0; word[i]!='\0'; i++){int index = word[i]-'a';if(curr->children[index]==NULL){
curr->children[index]=createNode();}
curr = curr->children[index];}
curr->isEndOfWord = true;}
bool search(structTrieNode* root,char* word){structTrieNode* curr = root;for(int i =0; word[i]!='\0'; i++){int index = word[i]-'a';if(curr->children[index]==NULL){return false;}
curr = curr->children[index];}return(curr !=NULL&& curr->isEndOfWord);}
bool startsWith(structTrieNode* root,char* prefix){structTrieNode* curr = root;for(int i =0; prefix[i]!='\0'; i++){int index = prefix[i]-'a';if(curr->children[index]==NULL){return false;}
curr = curr->children[index];}return true;}intmain(){structTrieNode* root =createNode();//inserting the elementsinsert(root,"Lamborghini");insert(root,"Mercedes-Benz");insert(root,"Land Rover");insert(root,"Maruti Suzuki");//Searching elementsprintf("Searching Cars\n");//Printing searched elementsprintf("Found? %d\n",search(root,"Lamborghini"));// Output: 1 (true)printf("Found? %d\n",search(root,"Mercedes-Benz"));// Output: 1 (true)printf("Found? %d\n",search(root,"Honda"));// Output: 0 (false)printf("Found? %d\n",search(root,"Land Rover"));// Output: 1 (true)printf("Found? %d\n",search(root,"BMW"));// Output: 0 (false) //Searching the elements the name starts with?printf("Cars name starts with\n");//Printing the elementsprintf("Does car name starts with 'Lambo'? %d\n",startsWith(root,"Lambo"));// Output: 1 (true)printf("Does car name starts with 'Hon'? %d\n",startsWith(root,"Hon"));// Output: 0 (false)printf("Does car name starts with 'Hy'? %d\n",startsWith(root,"Hy"));// Output: 0 (false)printf("Does car name starts with 'Mar'? %d\n",startsWith(root,"Mar"));// Output: 1 (true)printf("Does car name starts with 'Land'? %d\n",startsWith(root,"Land"));// Output: 1 (true) return0;}
Output
Searching Cars Found? 1 Found? 1 Found? 0 Found? 1 Found? 0 Cars name starts with Does car name starts with 'Lambo'? 1 Does car name starts with 'Hon'? 0 Does car name starts with 'Hy'? 0 Does car name starts with 'Mar'? 1 Does car name starts with 'Land'? 1
Leave a Reply