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.
//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.
//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.
//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.
Leave a Reply