Create a Word Auto-Completer in C using the Trie Data Structure

So first of all a few words about our basic structure, the trieā€¦

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

For example, in our case, our project involves alphabets with every inner node of the trie data structure representing a letter which means that each node has a unique path from the root (can have up to 26 children as the number of the Latin alphabet) that symbolizes a word.

 

In our project, in order to create our fancy auto-completer we will need three structures. Firstly we need the structure of the

inner nodes that store a character that represents the letter of this node, an array of 26 letters that will navigate through the next letter. Moreover to make our program more accurate we will use an array that stores the top leafs (top words) under this inner node and a leaf pointer that is going to show us that the path from the root until this inner node reflects a word. The leaf structure contains the frequency of this word (which is the parent of the leaf) and a pointer to the last letter of the word.

More