C Trie Data Structure 🚀

Welcome to our deep dive into the world of C Trie Data Structure! In this lesson, we'll explore this powerful and efficient data structure, understand its real-world applications, and learn how to implement it from scratch. Let's get started!

Understanding Trie 📝

A Trie, also known as a prefix tree or digital tree, is a tree-like data structure used to efficiently store and search for strings with a common prefix. It's particularly useful when dealing with large amounts of data, as it minimizes the number of comparisons required to find a matching string.

Why Use a Trie? 💡

Fast search: Trie allows for fast lookups due to its hierarchical structure and the absence of redundant data.
Efficient autocomplete: Trie is ideal for implementing autocomplete functions because it stores a collection of words with a common prefix.
Duplicate prevention: Trie ensures that no duplicate words are stored since each node stores only a character and a reference to the next level.

Implementing a C Trie 🎯

Now that we understand the concept, let's dive into the implementation. Here's a simple structure for our Trie nodes:

typedef struct TrieNode {
    int isEndOfWord;
    struct TrieNode* children[26];
} TrieNode;

Each TrieNode has an array of pointers to 26 children (corresponding to ASCII characters) and an isEndOfWord flag to indicate if the current word ends at this node.

Inserting Words into the Trie 📝

To insert a word into the Trie, we traverse through the Trie nodes, creating new nodes as necessary, and setting the isEndOfWord flag at the end.

void insert(TrieNode* root, const char* word) {
    TrieNode* currentNode = root;

    for (int level = 0; level < strlen(word); level++) {
        int index = word[level] - 'a';
        if (!currentNode->children[index]) {
            currentNode->children[index] = createNode();
        }
        currentNode = currentNode->children[index];
    }
    currentNode->isEndOfWord = 1;
}

Searching for Words in the Trie 🎯

Searching for a word in the Trie is similar to inserting but we check if the isEndOfWord flag is set at the last node.

int search(TrieNode* root, const char* word) {
    TrieNode* currentNode = root;

    for (int level = 0; level < strlen(word); level++) {
        int index = word[level] - 'a';
        if (!currentNode->children[index]) {
            return 0;
        }
        currentNode = currentNode->children[index];
    }
    return currentNode->isEndOfWord;
}

Implementing Wildcard Search 💡

To support wildcard search, we can modify the Trie structure and the search function to handle the wildcard character '*'.

typedef struct TrieWildcardNode {
    int isEndOfWord;
    struct TrieWildcardNode* children[27]; // 27 for ASCII characters and wildcard
} TrieWildcardNode;

int wildcardSearch(TrieWildcardNode* root, const char* word) {
    // ... wildcard search implementation ...
}

Quiz 🎯

That's it for our introductory lesson on C Trie Data Structure! With this knowledge, you're well-equipped to start implementing Tries in your own projects. Happy coding! 💻🚀