Author: admin

A suffix trie is a type of trie mainly used for representing all the suffixes of a string. It is a tree where each node represents the suffix of a string. The root node is the entire string, and each child node is a suffix of the string that’s one character shorter than the parent node’s suffix.

For example, consider the string “banana”. The suffix trie for this string would look like this:

             root
           /  | \
          b   a  n
         /    |   \
         a    n    a
        /     |     \
        n     a      n
       /      |       \
      a       n        a
     /        |         \
    n         a          $
   /          |
  a           $
 /
$

Each path from the root to a leaf node represents a suffix of the string. The leaf nodes represent the end of a suffix, and the dollar sign ($) is used to indicate the end of the string.

The children store entire word instead of characters.

Features of Suffix Tries

Following are the Features of Suffix Tries −

Operations on Suffix Tries

Some of the common operations on suffix tries include:

• Insertion: Insert a new suffix into the trie.
• Deletion: Remove a suffix from the trie.
• Search: Find a specific suffix in the trie.

Insertion Operation on Suffix Tries

We can insert a new suffix into the trie by following these steps:

1. Start at the root node.
2. For each character in the suffix:
    a. If the character is not in the current node's children, create a new node for the same.
    b. Then move to the child node corresponding to the character and repeat the process.
3. Repeat the process for all character in the suffix.
4. Mark the last node as a leaf node to indicate the end of the suffix.

Code for Insertion Operation

For example, to insert the suffix “ana” into the trie, we would follow these steps:

CC++JavaPython

// C Program to insert a suffix into a trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for trie nodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new trie nodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
   node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
      node->children[i]=NULL;}return node;}// Function to insert a suffix into the trievoidinsert(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){
         current->children[index]=createNode();}
      current = current->children[index];}
   current->isEndOfWord =1;}// Display the trievoiddisplay(structTrieNode* root,char str[],int level){if(root->isEndOfWord){
      str[level]='\0';printf("%s\n", str);}for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]!=NULL){
         str[level]= i +'a';display(root->children[i], str, level +1);}}}intmain(){structTrieNode* root =createNode();insert(root,"banana");insert(root,"ana");insert(root,"na");insert(root,"a");insert(root,"$");char str[20];// Allocating memory for string bufferdisplay(root, str,0);return0;}

Output

Following is the output of the above code:

a
ana
banana
na

Deletion and Search Operations on Suffix Tries

Deletion and search operations on suffix tries are similar to insertion. We can delete a suffix by removing the corresponding leaf node from the trie. To search for a specific suffix, we can traverse the trie from the root node to the leaf node corresponding to the suffix.

Following are the steps to delete a suffix from the trie:

1. Start at the root node.
2. For each character in the suffix:
    a. Move to the child node corresponding to the character.
3. Mark the last node as a non-leaf node to delete the suffix.

Following are the steps to search for a specific suffix in the trie:

1. Start at the root node.
2. For each character in the suffix:
    a. Move to the child node corresponding to the character.
3. Check if the last node is a leaf node to find the suffix.

Code for Deletion and Search Operations

Here is the code for deletion and search operations on suffix tries:

CC++JavaPython

// C Program to delete and search a suffix in a trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for trie nodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new trie nodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
   node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
      node->children[i]=NULL;}return node;}// Function to insert a suffix into the trievoidinsert(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){
         current->children[index]=createNode();}
      current = current->children[index];}
   current->isEndOfWord =1;}// Function to delete a suffix from the trievoiddelete(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){return;// Suffix not found}
      current = current->children[index];}
   current->isEndOfWord =0;}// Function to search for a suffix in the trieintsearch(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){return0;// Suffix not found}
      current = current->children[index];}return current->isEndOfWord;}intmain(){structTrieNode* root =createNode();insert(root,"banana");insert(root,"ana");insert(root,"na");insert(root,"a");insert(root,"$");printf("Search for 'ana': %s\n",search(root,"ana")?"Found":"Not found");delete(root,"ana");printf("After deletion:\n");printf("Search for 'ana': %s\n",search(root,"ana")?"Found":"Not found");printf("Search for 'na': %s\n",search(root,"na")?"Found":"Not found");return0;}

Output

Following is the output of the above code:

Search for 'ana': Found
After deletion:
Search for 'ana': Not found
Search for 'na': Found

Time Complexity of Suffix Tries

The time complexity of suffix tries depends on the operations performed:

• Insertion: O(n) for inserting a suffix of length n into the trie.
• Deletion: O(n)
• Search: O(n)

Applications of Suffix Tries

Suffix tries are used in various applications, including:

• Pattern matching and substring search algorithms
• Text indexing and searching
• Genomic sequence analysis
• Spell checking and correction
• Biological sequence analysis
• Information retrieval
• Compression algorithms

Conclusion

In this chapter, we discussed suffix tries, a type of trie used for representing all the suffixes of a string. We explored the structure of a suffix trie, its features, operations, and applications. Suffix tries are a powerful data structure for substring searches, pattern matching, and other string-related operations.

Compressed Trie is also known as Patricia Trie or Radix Tree. It is a type of trie data structure that is used for storing and retrieving keys in a dataset, where the keys are strings.

You can think of a compressed trie as a trie where the nodes with only one child are merged with their parent nodes. This helps in reducing the space complexity of the trie and makes it more efficient.

The compression of redundant nodes helps in memory management. This type of trie is used with applications that need space management.

Properties of Compressed Tries

Following are some of the properties of compressed tries:

• The nodes of compressed tries have at least two children.
• The edges of the trie are labeled with characters.
• The keys are stored in the leaves of the trie.

Representation of Compressed Tries

Now, let’s see how a compressed trie is represented:

It is represented as a tree where each node has a label and a list of children. The edges of the tree are labeled with characters. The keys are stored in the leaves of the tree.

Here is an example of a compressed trie:

    (root)
      |
     b
     |
    e, i
    |   \
  ar, ll  d
      \    \
       l     l
      /       \
    d, ll    bull

In the above example, the keys “bear”, “bell”, “bid”, “bull” are stored in the leaves of the trie.

Operations on Compressed Tries

We can perform the following operations on compressed tries:

• Insert: Inserting a new key into the trie.
• Search: Searching for a key in the trie.
• Delete: Deleting a key from the trie.

Insert Operation on Compressed Tries

For insertion of a new key into the compressed trie, we need to follow these steps:

Algorithm for Insert Operation

Following is the algorithm for inserting a new key into the compressed trie:

Insert the new key into the trie.
If the node has only one child, merge it with its parent.

Code for Insert Operation

Now, let’s implement the insert operation in a compressed trie. For this, first we need to define the structure of the trie node then implement the insert operation.

CC++JavaPython

//C Program to perform Insert Operation on Compressed Trie#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26// Structure for Trie NodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new Trie NodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
   node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
      node->children[i]=NULL;}return node;}// Function to insert a key into the Trievoidinsert(structTrieNode* root,char* key){structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(!temp->children[index]){
         temp->children[index]=createNode();}
      temp = temp->children[index];}
   temp->isEndOfWord =1;}voiddisplay(structTrieNode* root,char str[],int level){if(root->isEndOfWord){
      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(){structTrieNode* root =createNode();char keys[][8]={"bear","bell","bid","bull"};for(int i =0; i <4; i++){insert(root, keys[i]);}char str[20];display(root, str,0);return0;}

Output

Following is the output of the above code:

bear
bell
bid
bull

Search Operation on Compressed Tries

For searching a key in the compressed trie, we need to follow these steps:

Algorithm for Search Operation

Following is the algorithm for searching a key in the compressed trie:

Search for the key in the trie.
If the key is found, return true.
Otherwise, return false.

Code for Search Operation

Now, let’s implement the search operation in a compressed trie. For this, we need to define the structure of the trie node and then implement the search operation.

CC++JavaPython

//C Program to perform Search Operation on Compressed Trie#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26// Structure for Trie NodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new Trie NodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
   node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
      node->children[i]=NULL;}return node;}// Function to insert a key into the Trievoidinsert(structTrieNode* root,char* key){structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(!temp->children[index]){
         temp->children[index]=createNode();}
      temp = temp->children[index];}
   temp->isEndOfWord =1;}// Function to search a key in the Trieintsearch(structTrieNode* root,char* key){structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(!temp->children[index]){return0;}
      temp = temp->children[index];}return(temp !=NULL&& temp->isEndOfWord);}voiddisplay(structTrieNode* root,char str[],int level){if(root->isEndOfWord){
      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(){structTrieNode* root =createNode();char keys[][8]={"bear","bell","bid","bull"};for(int i =0; i <4; i++){insert(root, keys[i]);}char str[20];display(root, str,0);char key[]="bell";if(search(root, key)){printf("%s is present in the trie.\n", key);}else{printf("%s is not present in the trie.\n", key);}return0;}

Output

Following is the output of the above code:

bear
bell
bid
bull
bell is present in the trie.

Delete Operation on Compressed Tries

For deleting a key from the compressed trie, we need to follow these steps:

Algorithm for Delete Operation

Following is the algorithm for deleting a key from the compressed trie:

Search for the key in the trie.
If the key is found, mark the last node as not the end of the word.
If the last node has no children, delete it.

Code for Delete Operation

Now, let’s implement the delete operation in a compressed trie. For this, we need to define the structure of the trie node and then implement the delete operation.

CC++JavaPython

//C Program to perform Delete Operation on Compressed Trie#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26// Structure for Trie NodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new Trie NodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
   node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
      node->children[i]=NULL;}return node;}// Function to insert a key into the Trievoidinsert(structTrieNode* root,char* key){structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(!temp->children[index]){
         temp->children[index]=createNode();}
      temp = temp->children[index];}
   temp->isEndOfWord =1;}// Function to search a key in the Trieintsearch(structTrieNode* root,char* key){structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';if(!temp->children[index]){return0;}
      temp = temp->children[index];}return(temp !=NULL&& temp->isEndOfWord);}// Function to delete a key from the Trievoiddelete(structTrieNode* root,char* key){if(!search(root, key)){return;}structTrieNode* temp = root;for(int i =0; i <strlen(key); i++){int index = key[i]-'a';
      temp = temp->children[index];}
   temp->isEndOfWord =0;}voiddisplay(structTrieNode* root,char str[],int level){if(root->isEndOfWord){
      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(){structTrieNode* root =createNode();char keys[][8]={"bear","bell","bid","bull"};for(int i =0; i <4; i++){insert(root, keys[i]);}char str[20];display(root, str,0);char key[]="bell";delete(root, key);printf("Trie after deletion:\n");display(root, str,0);if(search(root, key)){printf("%s is present in the trie.\n", key);}else{printf("%s is not present in the trie.\n", key);}return0;}

Output

Following is the output of the above code:

bear
bell
bid
bull
bell is not present in the trie.

Applications of Compressed Tries

Compressed tries are used in various applications, such as:

• Spell checkers: In spell checkers, compressed tries are used to store the dictionary of words.
• Text editors
• Routing tables in computer networks
• Genome sequence analysis
• String matching algorithms

Conclusion

In this chapter, we learned about compressed tries, which are used to store a large number of strings efficiently. We discussed the structure of a compressed trie, the insert operation, search operation, and delete operation on a compressed trie. We also implemented these operations in C, C++, Java, and Python programming languages.

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.

CC++JavaPython

// 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.

CC++JavaPython

// 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.

CC++JavaPython

// 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.

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 −

CC++JavaPython

#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 −

CC++JavaPython

//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 −

CC++JavaPython

//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