Trie Implementation in C – Insert, Search and Delete
Implement insert, search, and delete operations on Trie data structure. Assume that the input consists of only lowercase letters a–z.
Overview of Trie
Trie is a tree-based data structure, which is used for efficient retrieval of a key in a large dataset of strings. Unlike a binary search tree, where a node stores the key associated with that node, the Trie node’s position in the tree defines the key with which it is associated, and the key is only associated with the leaves. It is also known as a prefix tree as all descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
Representation of Trie
There are several ways to represent a Trie, corresponding to different trade-offs between memory use and operations speed. The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers). The Trie node also maintains a flag that specifies whether it corresponds to the key’s end or not.
As illustrated in the following figure, each key is represented in the Trie as a path from the root to the internal node or a leaf:
Implementation of Trie
Insertion proceeds by walking the Trie according to the string to be inserted, then appending new nodes for the suffix of the string that is not contained in the Trie. Searching also proceeds the similar way by walking the Trie according to the string to be searched, returning false if the string is not found. Deletion is a bit complicated. The idea is to delete the key in a bottom-up manner using recursion. Special care has to be taken while deleting the key as it can be the prefix of another key, or its prefix can be another key in Trie.
Following is the C implementation of the Trie data structure, which supports insertion, deletion, and search operations. The implementation currently supports only lowercase English characters (a – z), but it can be easily extended to support any set of characters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 |
#include <stdio.h> #include <stdlib.h> // Define the character size #define CHAR_SIZE 26 // Data structure to store a Trie node struct Trie { int isLeaf; // 1 when the node is a leaf node struct Trie* character[CHAR_SIZE]; }; // Function that returns a new Trie node struct Trie* getNewTrieNode() { struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie)); node->isLeaf = 0; for (int i = 0; i < CHAR_SIZE; i++) { node->character[i] = NULL; } return node; } // Iterative function to insert a string into a Trie void insert(struct Trie *head, char* str) { // start from the root node struct Trie* curr = head; while (*str) { // create a new node if the path doesn't exist if (curr->character[*str - 'a'] == NULL) { curr->character[*str - 'a'] = getNewTrieNode(); } // go to the next node curr = curr->character[*str - 'a']; // move to the next character str++; } // mark the current node as a leaf curr->isLeaf = 1; } // Iterative function to search a string in a Trie. It returns 1 // if the string is found in the Trie; otherwise, it returns 0. int search(struct Trie* head, char* str) { // return 0 if Trie is empty if (head == NULL) { return 0; } struct Trie* curr = head; while (*str) { // go to the next node curr = curr->character[*str - 'a']; // if the string is invalid (reached end of a path in the Trie) if (curr == NULL) { return 0; } // move to the next character str++; } // return 1 if the current node is a leaf and the // end of the string is reached return curr->isLeaf; } // Returns 1 if a given Trie node has any children int hasChildren(struct Trie* curr) { for (int i = 0; i < CHAR_SIZE; i++) { if (curr->character[i]) { return 1; // child found } } return 0; } // Recursive function to delete a string from a Trie int deletion(struct Trie **curr, char* str) { // return 0 if Trie is empty if (*curr == NULL) { return 0; } // if the end of the string is not reached if (*str) { // recur for the node corresponding to the next character in // the string and if it returns 1, delete the current node // (if it is non-leaf) if (*curr != NULL && (*curr)->character[*str - 'a'] != NULL && deletion(&((*curr)->character[*str - 'a']), str + 1) && (*curr)->isLeaf == 0) { if (!hasChildren(*curr)) { free(*curr); (*curr) = NULL; return 1; } else { return 0; } } } // if the end of the string is reached if (*str == '\0' && (*curr)->isLeaf) { // if the current node is a leaf node and doesn't have any children if (!hasChildren(*curr)) { free(*curr); // delete the current node (*curr) = NULL; return 1; // delete the non-leaf parent nodes } // if the current node is a leaf node and has children else { // mark the current node as a non-leaf node (DON'T DELETE IT) (*curr)->isLeaf = 0; return 0; // don't delete its parent nodes } } return 0; } // Trie implementation in C – Insertion, Searching, and Deletion int main() { struct Trie* head = getNewTrieNode(); insert(head, "hello"); printf("%d ", search(head, "hello")); // print 1 insert(head, "helloworld"); printf("%d ", search(head, "helloworld")); // print 1 printf("%d ", search(head, "helll")); // print 0 (Not present) insert(head, "hell"); printf("%d ", search(head, "hell")); // print 1 insert(head, "h"); printf("%d \n", search(head, "h")); // print 1 + newline deletion(&head, "hello"); printf("%d ", search(head, "hello")); // print 0 (hello deleted) printf("%d ", search(head, "helloworld")); // print 1 printf("%d \n", search(head, "hell")); // print 1 + newline deletion(&head, "h"); printf("%d ", search(head, "h")); // print 0 (h deleted) printf("%d ", search(head, "hell")); // print 1 printf("%d\n", search(head, "helloworld")); // print 1 + newline deletion(&head, "helloworld"); printf("%d ", search(head, "helloworld")); // print 0 printf("%d ", search(head, "hell")); // print 1 deletion(&head, "hell"); printf("%d\n", search(head, "hell")); // print 0 + newline if (head == NULL) { printf("Trie empty!!\n"); // Trie is empty now } printf("%d ", search(head, "hell")); // print 0 return 0; } |
Output:
1 1 0 1 1
0 1 1
0 1 1
0 1 0
Trie empty!!
0
Performance of Trie
The time complexity of a Trie data structure for insertion/deletion/search operation is just O(n), where n is key length.
The space complexity of a Trie data structure is O(N × M × C), where N is the total number of strings, M is the maximum length of the string, and C is the alphabet’s size. Please refer to the following post for a memory-efficient implementation of the Trie:
Memory Efficient C++ Implementation of Trie – Insert, Search, and Delete
Applications of Trie
Numerous Trie data structure applications take advantage of a Trie’s ability to quickly search, insert, and delete entries.
Trie has several advantages over binary search trees. It can also replace a hash table as lookup is generally faster in the Trie, even in the worst case. Also, there are no collisions of different keys in a Trie, and a Trie can provide an alphabetical ordering of the entries by key.
A Trie’s common application is storing a predictive text or autocomplete dictionaries, such as found on a mobile telephone or search engines. Autocomplete (or word completion) is a feature in which an application predicts the rest of a word the user is typing.
The spell checker flags words in a document that may not be spelled correctly. Spell checkers are commonly used in word processors (like MS Word), email clients, search engines, etc.
Lexicographic sorting of a set of keys can be accomplished with a simple Trie-based algorithm. We initially insert all keys into a Trie and then print all keys in the Trie by performing preorder traversal (depth–first traversal), resulting in a lexicographically increasing order.
Routers use the longest prefix match algorithm in Internet Protocol (IP) networking to select an entry from a forwarding table.
Also see:
References: https://en.wikipedia.org/wiki/Trie
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)