data-structures Trie (Prefix Tree/Radix Tree) Implementation of Trie

Example

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.

Node:

The nodes will consist of:

1. Variable for End-Mark.
2. Pointer Array to the next Node.

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[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

Every element in next[] array points to another node. next[0] points to the node sharing edge-a, next[1] 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.

Insertion:

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.

Searching:

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.

Deletion:

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.