Trie data structure

Trie data structure

The term “trie” comes from the word “retrieval” which means getting information. The trie data structure is a sorted extension of tree-based data structure. The trie data structure is used to store the set of strings. In the trie data structure, the address variable or pointer are same as the alphabet in each node. The trie data structure is able to find or search a word in the dictionary by the help of the prefix of given word. We can say the trie data structure is an efficient information retrieval data structure. By the help of it, we can minimize search complexities. In trie data structure, all the children are present in it have a common prefix of the string associated with that parent node and the root node of it contain the null or empty string. The trie data structure is also called the prefix tree or digital tree.

Properties of the Trie for a set of the string:

• Trie is a tree.
• Trie stores a set of string.
• Trie does not contain any value at root level.
• In trie data structure, each child of nodes is sorted in dictionary order.
• A node in trie data structure can contain utmost 26 children ( A to Z).

Operations on Trie: -

We can perform three operation on the Trie

• Insert a node into the trie.
• Delete a node from the trie.
• Search a node

• Insert of a node in the Trie

• For insertion a node in trie, each letter of input key is inserted as separate trie node.
• In trie data structure, the key character or letter behaves as the index into the array children.
• If the key which we want to input in trie data structure is not there or an extension of existing key then we will construct non-existing nodes of the key and we will mark end of word for the last node.
• In trie data structure, the input key is prefix of already added key then we will mark the last node as end of the word.
• The number of characters determines the depth of the trie data structure.

New node insertion implementation on Trie: -

     void insert(String word) {
         TrieNode pointer = root;
         for (char l : word.toCharArray()) {
             pointer = pointer.getNode().computeIfAbsent(l, c -> new TrieNode());
         }
         pointer.setEnding(true);
     }
     boolean delete(String word) {
         return delete(root, word, 0);
     } 

• Searching a node in Trie

In this, we will see searching a node in a trie. The search operation is similar as the insertion operation in a trie. In search operation, we find a key in the trie. The implementation of searching operation in trie is given below.

Searching implementation on Trie: -

     boolean search(String word) {
         TrieNode pointer = root;
         for (int i = 0; i < word.length(); i++) {
             char ch = word.charAt(i);
             TrieNode node = pointer.getNode().get(ch);
             if (node == null) {
                 return false;
             }
             pointer = node;
         }
         return pointer.isEnding();
     } 

• Deletion of a node in the Trie

Now we will be discussing how can we delete a node from the trie.

• In the trie, if key is not there then the delete operation will be stopped.
• In the trie, if the key is there then delete the key from the trie.

Node deletion implementation on Trie: -

     private boolean delete(TrieNode pointer, String word, int index) {
         if (index == word.length()) {
             if (!pointer.isEnding()) {
                 return false;
             }
             pointer.setEnding(false);
             return pointer.getNode().isEmpty();
         }
         char ch = word.charAt(index);
         TrieNode node = pointer.getNode().get(ch);
         if (node == null) {
             return false;
         }
         boolean check = delete(node, word, index + 1) && !node.isEnding();
         if (check) {
             pointer.getNode().remove(ch);
             return pointer.getNode().isEmpty();
         }
         return false;
     } 

Applications of Trie: -

• Spell Checker

We can use the trie data structure as spell checker mechanism. In this, firstly it will check that word in a dictionary and it will suggest the words according to desired order. The trie data structure is efficient for searching the words into dictionary and also used to make an algorithm to include a collection of relevant words or suggestions.

• Auto-complete

Auto-complete functionality is most popular functionality now days which used by text-editors, internet browsers and mobile applications. In this, when type or search something then it provides some suggestions based on user previous history.

Trie gives an alphabetical filter of strings entries by the key of the nodes.

• Browser history

Trie is used to the URL or give the URL suggestion in the browser because most of browser keeps a history of URL’s of the website which the user has visited.

Advantages of Trie

• In trie data structure, we can perform faster insert operation and search operation as compared to the hashtable and binary search tree.
• Trie also provides an alphabetical filter of entries with the help of key of the node.

Disadvantages of Trie

• Extra memory consumed by trie to store the strings.
• Trie is slower as compared to hash table.

Trie implementation: -

 import java.util.HashMap;
 import java.util.Map;
 public class Triee {
     private TrieNode root;
     Triee() {
         root = new TrieNode();
     }
     class TrieNode {
     private final Map<Character, TrieNode> children = new HashMap<>();
     private boolean ending;
     Map<Character, TrieNode> getNode() {
         return children;
     }
     boolean isEnding() {
         return ending;
     }
     void setEnding(boolean ending) {
         this.ending = ending;
     }
 }
     void insert(String word) {
         TrieNode pointer = root;
         for (char l : word.toCharArray()) {
             pointer = pointer.getNode().computeIfAbsent(l, c -> new TrieNode());
         }
         pointer.setEnding(true);
     }
     boolean delete(String word) {
         return delete(root, word, 0);
     }
     boolean search(String word) {
         TrieNode pointer = root;
         for (int i = 0; i < word.length(); i++) {
             char ch = word.charAt(i);
             TrieNode node = pointer.getNode().get(ch);
             if (node == null) {
                 return false;
             }
             pointer = node;
         }
         return pointer.isEnding();
     }
     boolean isEmpty() {
         return root == null;
     }
     private boolean delete(TrieNode pointer, String word, int index) {
         if (index == word.length()) {
             if (!pointer.isEnding()) {
                 return false;
             }
             pointer.setEnding(false);
             return pointer.getNode().isEmpty();
         }
         char ch = word.charAt(index);
         TrieNode node = pointer.getNode().get(ch);
         if (node == null) {
             return false;
         }
         boolean check = delete(node, word, index + 1) && !node.isEnding();
         if (check) {
             pointer.getNode().remove(ch);
             return pointer.getNode().isEmpty();
         }
         return false;
     }
             public static void main(String[] args) {
                         boolean res;
                         Triee trie = new Triee();
                         trie.insert("art");
                         trie.insert("bunny");
                         trie.insert("buck");
                         trie.insert("dog");
                         trie.insert("Apostate");
                         res = trie.search("bunny");
                         System.out.println(res);
                         res = trie.search("duck");
                         System.out.println(res);
             }
 } 

Output: -

true

false

Time Complexity:

The time complexity of insert, search and delete are O(n), O(n), O(c*n) respectively, where n is the length of input string and c is the number of alphabets.