Trie

Trie Implementation

Pinterest LinkedIn Tumblr

Trie or prefix tree is an ordered tree data structure that allows strings with similar chars to prefix to use the same prefix data and only the remaining stored in separate data. A trie is data structure uses for storing the strings in which there is one node for every common prefix. Trie word comes from retrieval.

Write a program to implement Trie or prefix tree data structure?

Algorithm Explanation

Add operation insert the string values into the binary search tree with Trie properties.
Remove operation delete the item from the tree. The ismember operation checks whether the data is available in the trie.
Boyer-moore algorithm can be used for text processing and pattern matching. If the text is large, It can be searched using pattern matching.
Each node in trie labeled with a character and children nodes are ordered alphabetically.
If the data access from hard disk drive, the access time is more compare than accessing from main memory.

Source Code

package com.dsacode.DataStructre.trie;
 
import java.util.Arrays;
 
class TrieNode {
    char letter;
    TrieNode[] links;
    boolean fullWord;
 
    TrieNode(char letter, boolean fullWord) {
        this.letter = letter;
        this.fullWord = fullWord;
        links = new TrieNode[26];
    }
}
 
public class TrieImp {
 
    static TrieNode createTree() {
        return (new TrieNode('\0', false));
    }
 
    static void insertWord(TrieNode root, String word) {
        int offset = 97;
        int l = word.length();
        char[] letters = word.toCharArray();
        TrieNode curNode = root;
 
        for (int i = 0; i < l; i++) {
            if (curNode.links[letters[i] - offset] == null)
                curNode.links[letters[i] - offset] = new TrieNode(letters[i],
                        i == l - 1 ? true : false);
            curNode = curNode.links[letters[i] - offset];
        }
    }
 
    static boolean find(TrieNode root, String word) {
        char[] letters = word.toCharArray();
        int l = letters.length;
        int offset = 97;
        TrieNode curNode = root;
 
        int i;
        for (i = 0; i < l; i++) {
            if (curNode == null)
                return false;
            curNode = curNode.links[letters[i] - offset];
        }
 
        if (i == l && curNode == null)
            return false;
 
        if (curNode != null && !curNode.fullWord)
            return false;
 
        return true;
    }
 
    static void printTree(TrieNode root, int level, char[] branch) {
        if (root == null)
            return;
 
        for (int i = 0; i < root.links.length; i++) {
            branch[level] = root.letter;
            printTree(root.links[i], level + 1, branch);
        }
 
        if (root.fullWord) {
            for (int j = 1; j <= level; j++)
                System.out.print(branch[j]);
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
        TrieNode tree = createTree();
         
         
        String[] words = { "an", "ant", "all", "allot", "alloy", "aloe", "are",
                "ate", "be" };
        System.out.println("List of Words from array:" + Arrays.toString(words));
         
        for (int i = 0; i < words.length; i++)
            insertWord(tree, words[i]);
 
        char[] branch = new char[50];
        System.out.println("Print words from Trie:" );
        printTree(tree, 0, branch);
 
        String searchWord = "all";
        System.out.print("Find word 'all' from Trie: ");
        if (find(tree, searchWord)) {
            System.out.print("The word was found");
        } else {
            System.out.print("The word was NOT found");
        }
    }
 
}

Output

List of Words from array:[an, ant, all, allot, alloy, aloe, are, ate, be]
Print words from Trie:
allot
alloy
all
aloe
ant
an
are
ate
be
Find word 'all' from Trie: The word was found

Source Explanation

String array initialized with the list of strings and print the strings before insert to the trie. The insert operation inserts all the words from character into the trie.
PrintTrie operation print all the characters form trie.
Find operation takes the root node of the trie. If the string available in the trie, it returns true. Otherwise, it returns false.

Real Applications

  1. IP routing
  2. Find all words beginning with ‘a’ or ‘axe’ so on.
  3. Real time Auto Complete
  4. Dictionary representation
  5. Full text search
  6. Sub string searching
  7. Storing strings over an alphabet.
  8. Spelling-checking programs
  9. Web Search Engine
  10. Word matching
  11. Prefix matching

Reference

  1. https://en.wikipedia.org/wiki/Trie
  2. https://www.cs.bu.edu/teaching/c/tree/trie
  3. http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr45102/Tries.pdf
  4. http://software.ucv.ro/~cmihaescu/ro/laboratoare/SDA/docs/trie.pdf

Write A Comment