C Program to Implement Trie
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct w3wikiTrieNode {
struct w3wikiTrieNode *children[ALPHABET_SIZE];
bool isendofword;
};
typedef struct w3wikiTrieNode w3wikiTrieNode;
w3wikiTrieNode *createNode() {
w3wikiTrieNode *node = (w3wikiTrieNode *)malloc(sizeof(w3wikiTrieNode));
node->isendofword = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
node->children[i] = NULL;
}
return node;
}
void insert(w3wikiTrieNode *root, const char *key) {
w3wikiTrieNode *current = root;
for (int i = 0; i < strlen(key); i++) {
int index = key[i] - 'a';
if (current->children[index] == NULL) {
current->children[index] = createNode();
}
current = current->children[index];
}
current->isendofword = true;
}
bool search(w3wikiTrieNode *root, const char *key) {
w3wikiTrieNode *current = root;
for (int i = 0; i < strlen(key); i++) {
int index = key[i] - 'a';
if (current->children[index] == NULL) {
return false;
}
current = current->children[index];
}
return (current != NULL && current->isendofword);
}
bool isempty(w3wikiTrieNode *root) {
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (root->children[i] != NULL) {
return false;
}
}
return true;
}
w3wikiTrieNode *deleteHelper(w3wikiTrieNode *root, const char *key, int depth) {
if (root == NULL) {
return NULL;
}
if (depth == strlen(key)) {
if (root->isendofword) {
root->isendofword = false;
}
if (isempty(root)) {
free(root);
root = NULL;
}
return root;
}
int index = key[depth] - 'a';
root->children[index] = deleteHelper(root->children[index], key, depth + 1);
if (isempty(root) && !root->isendofword) {
free(root);
root = NULL;
}
return root;
}
void deletekey(w3wikiTrieNode *root, const char *key) {
deleteHelper(root, key, 0);
}
int main() {
w3wikiTrieNode *root = createNode();
insert(root, "hello");
insert(root, "world");
printf("%s\n", search(root, "hello") ? "Found" : "Not Found");
printf("%s\n", search(root, "world") ? "Found" : "Not Found");
printf("%s\n", search(root, "geeks") ? "Found" : "Not Found");
deletekey(root, "hello");
printf("%s\n", search(root, "hello") ? "Found" : "Not Found");
return 0;
}
In this code, as we entered the ‘hello’ and ‘world’ in the trie, the output for searching of ‘hello’ and ‘world’ will be True i.e. ‘Found’ but for ‘geeks’ it will be ‘Not Found’. After deleting the ‘hello’ from trie , search result for trie will also be ‘Not Found’.
Implementation of Trie (Prefix Tree) in C
The Trie data structure is a tree-based data structure that is used to store the set of strings. Trie is also known as Prefix Tree or Digital Tree. Trie is used to store the strings in alphabetical order.
- Every Node can have a maximum of 26 children (i.e. a to z are 26 alphabets).
- The root Node is always a Null node.
- Each Node stores only one alphabet.
- Every Node is stored in an alphabetical Order
- Searching for words is done with the help of prefixes of words.