Before reading this example, it is highly recommended that you read Introduction to Trie first.
One of the easiest ways of implementing Trie is using linked list.
The nodes will consist of:
The End-Mark variable will simply denote whether it is an end-point or not. The pointer array will denote all the possible edges that can be created. For English alphabets, the size of the array will be 26, as maximum 26 edges can be created from a single node. At the very beginning each value of pointer array will be NULL and the end-mark variable will be false.
Node: Boolean Endmark Node *next Node() endmark = false for i from 0 to 25 next[i] := NULL endfor endNode
Every element in next array points to another node. next points to the node sharing edge-a, next points to the node sharing edge-b and so on. We have defined the constructor of Node to initialize Endmark as false and put NULL in all the values of next pointer array.
To create Trie, at first we'll need to instantiate root. Then from the root, we'll create other nodes to store information.
Procedure Insert(S, root): // s is the string that needs to be inserted in our dictionary curr := root for i from 1 to S.length id := S[i] - 'a' if curr -> next[id] == NULL curr -> next[id] = Node() curr := curr -> next[id] endfor curr -> endmark = true
Here we are working with a-z. So to convert their ASCII values to 0-25, we subtract the ASCII value of 'a' from them. We will check if current node (curr) has an edge for the character at hand. If it does, we move to the next node using that edge, if it doesn't we create a new node. At the end, we change the endmark to true.
Procedure Search(S, root) // S is the string we are searching curr := root for i from 1 to S.length id := S[i] - 'a' if curr -> next[id] == NULL Return false curr := curr -> id Return curr -> endmark
The process is similar to insert. At the end, we return the endmark. So if the endmark is true, that means the word exists in the dictionary. If it's false, then the word doesn't exist in the dictionary.
This was our main implementation. Now we can insert any word in trie and search for it.
Sometimes we will need to erase the words that will no longer be used to save memory. For this purpose, we need to delete the unused words:
Procedure Delete(curr): //curr represents the current node to be deleted for i from 0 to 25 if curr -> next[i] is not equal to NULL delete(curr -> next[i]) delete(curr) //free the memory the pointer is pointing to
This function goes to all the child nodes of curr, deletes them and then curr is deleted to free the memory. If we call delete(root), it will delete the whole Trie.
Trie can be implemented using Arrays too.