Tries are tree-like data structures that are mainly used for storing dynamic set of strings or associative arrays where the keys are usually strings. The word “trie” comes from the word “retrieval”.
We already discussed the basic concepts of tries in Tries chapter. In this chapter, we will discuss the standard tries in data structures.
What is Standard Trie?
Children of a node are stored in a certain order such as dictionary order (alphabetical) or ASCII order. The order des on the use cases. For example, if the trie is used for a dictionary, the children are stored in alphabetical order.
Let’s understand with an example.
We have an array of Strings.
{cat, car, dog, doll}
The structure of the trie for these strings would be
(root)
/\
/ \
/ \
/ \
c d
/ \ / \
a a o o
/ \ / \
t r l g
/
l
The above example shows the standard trie structure for the strings {cat, car, dog, doll}. The root node is empty and the children are stored in alphabetical order.
In the Standard Trie, a string can be traced from the root node to the node where the strings. The node is marked as a leaf node.
Operations on Standard Trie
There are mainly three operations that can be performed on a standard trie:
- Insert: Inserting a new string in the trie.
- Search: Searching a string in the trie.
- Delete: Deleting a string from the trie.
Implementation of Standard Trie
For implementing the standard trie, we need to create a structure for the trie node. The trie node contains an array of pointers to the children nodes and a flag to mark the of the string.
Now, let’s implement the standard trie, which supports the above operations.
Insert Operation on Standard Trie
Inserting a new string in the Standard Trie is done by inserting the characters of the string one by one. The characters are inserted in the trie in the order of the string. The last character of the string is marked as a leaf node.
Algorithm for Insert Operation in Standard Trie
Following is the algorithm for the insert operation in the standard trie:
1.Traverse the trie from the root node. 2.Insert the characters of the string one by one. 3.Mark the last character of the string as a leaf node.
Code for Insert Operation in Standard Trie
Let’s see the code for the insert operation in the standard trie using C, C++, Java, and Python programming languages.
// C Program to perform Insert Operation in Standard Trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for Trie NodestructTrieNode{structTrieNode*children[ALPHABET_SIZE];int iOfWord;};// Function to create a new Trie NodestructTrieNode*createNode(){structTrieNode*newNode =(structTrieNode*)malloc(sizeof(structTrieNode));
newNode->iOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
newNode->children[i]=NULL;}return newNode;}// Function to insert a string in the Trievoidinsert(structTrieNode*root,char*key){structTrieNode*temp = root;for(int i =0; key[i]!='\0'; i++){int index = key[i]-'a';if(!temp->children[index]){
temp->children[index]=createNode();}
temp = temp->children[index];}
temp->iOfWord =1;}voiddisplay(structTrieNode*root,char str[],int level){if(root->iOfWord){
str[level]='\0';printf("%s\n", str);}for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]){
str[level]= i +'a';display(root->children[i], str, level +1);}}}// Main functionintmain(){char*keys[]={"cat","car","dog","doll"};int n =sizeof(keys)/sizeof(keys[0]);structTrieNode*root =createNode();for(int i =0; i < n; i++){insert(root, keys[i]);}printf("Inserted Strings are:\n");char str[26];display(root, str,0);return0;}
Output
Following is the output obtained −
Inserted Strings are: car cat dog doll
Search Operation on Standard Trie
Searching a string in the Standard Trie is done by traversing the trie from the root node to the node where the strings. If the string is found in the trie, then the search operation returns true; otherwise, it returns false.
Algorithm for Search Operation in Standard Trie
Following is the algorithm for the search operation in the Standard Trie:
1.Traverse the trie from the root node. 2.Search the characters of the string one by one. 3.If the string is found, return true. 4.If the string is not found, return false.
Code for Search Operation in Standard Trie
Following is the code for the search operation in the Standard Trie using C, C++, Java, and Python programming languages.
// C Program to perform Search Operation in Standard Trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for Trie NodestructTrieNode{structTrieNode*children[ALPHABET_SIZE];int iOfWord;};// Function to create a new Trie NodestructTrieNode*createNode(){structTrieNode*newNode =(structTrieNode*)malloc(sizeof(structTrieNode));
newNode->iOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
newNode->children[i]=NULL;}return newNode;}// Function to insert a string in the Standard Trievoidinsert(structTrieNode*root,char*key){structTrieNode*temp = root;for(int i =0; key[i]!='\0'; i++){int index = key[i]-'a';if(!temp->children[index]){
temp->children[index]=createNode();}
temp = temp->children[index];}
temp->iOfWord =1;}// Function to search a string in the Standard Trieintsearch(structTrieNode*root,char*key){structTrieNode*temp = root;for(int i =0; key[i]!='\0'; i++){int index = key[i]-'a';if(!temp->children[index]){return0;}
temp = temp->children[index];}return temp !=NULL&& temp->iOfWord;}intmain(){char*keys[]={"cat","car","dog","doll"};int n =sizeof(keys)/sizeof(keys[0]);structTrieNode*root =createNode();for(int i =0; i < n; i++){insert(root, keys[i]);}search(root,"cat")?printf("Found\n"):printf("Not Found\n");return0;}
Output
The output obtained is as follows −
Found
Delete Operation on Standard Trie
Deleting a string from the Standard Trie is done by deleting the characters of the string one by one. The characters are deleted in the order of the string. The last character of the string is marked as a non-leaf node.
Algorithm for Delete Operation in Standard Trie
Following is the algorithm for the delete operation in the Standard Trie:
1.Traverse the trie from the root node. 2.Delete the characters of the string one by one. 3.Mark the last character of the string as a non-leaf node.
Code for Delete Operation in Standard Trie
Let’s see the code for the delete operation in the Standard Trie using C, C++, Java, and Python programming languages.
// C Program to perform Delete Operation in Standard Trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26structTrieNode{structTrieNode*children[ALPHABET_SIZE];int iOfWord;};structTrieNode*createNode(){structTrieNode*newNode =(structTrieNode*)malloc(sizeof(structTrieNode));
newNode->iOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
newNode->children[i]=NULL;}return newNode;}voidinsert(structTrieNode*root,char*key){structTrieNode*temp = root;for(int i =0; key[i]!='\0'; i++){int index = key[i]-'a';if(!temp->children[index]){
temp->children[index]=createNode();}
temp = temp->children[index];}
temp->iOfWord =1;}intdelete(structTrieNode*root,char*key,int depth){if(root ==NULL){return0;}if(key[depth]=='\0'){if(root->iOfWord){
root->iOfWord =0;}for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]){return0;}}free(root);return1;}int index = key[depth]-'a';if(delete(root->children[index], key, depth +1)){
root->children[index]=NULL;if(!root->iOfWord){for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]){return0;}}free(root);return1;}}return0;}voiddisplay(structTrieNode*root,char str[],int level){if(root ==NULL){return;}if(root->iOfWord){
str[level]='\0';printf("%s\n", str);}for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]){
str[level]= i +'a';display(root->children[i], str, level +1);}}}intmain(){char*keys[]={"cat","car","dog","doll"};int n =sizeof(keys)/sizeof(keys[0]);structTrieNode*root =createNode();for(int i =0; i < n; i++){insert(root, keys[i]);}printf("Before Deletion:\n");char str[20];display(root, str,0);delete(root,"car",0);printf("\nAfter Deletion:\n");display(root, str,0);return0;}
Output
The output obtained is as follows −
Before Deletion: car cat dog doll After Deletion: cat dog doll
Time Complexity of Standard Trie
Following is the time complexity of the Standard Trie:
- Insert Operation: O(n), where n is the length of the string.
- Search Operation: O(n).
- Delete Operation: O(n).
Applications of Standard Trie
Standard Trie is used in various applications such as:
- Spell Checker
- Auto-Complete
- Dictionary
- IP Routing
- Network Routing
- Prefix Matching
These are some of the applications where Standard Trie is used.
Conclusion
In this chapter, we discussed the Standard Trie in data structures. The structure of the Standard Trie, the operations that can be performed on the Standard Trie, and the implementation of the Standard Trie. We also discussed the applications of the Standard Trie.
Leave a Reply