Trie data structure

A trie is a tree like data structure. Trie is also called as prefix tree.

In this article, we going to see three main operations of trie data structure. They are:

  1. Insert
  2. Delete
  3. Search

TrieNode

  class TrieNode {

    int terminating;

    TrieNode[] trieNodes = new TrieNode[26];

    public TrieNode next(final char c) {
        return trieNodes[c - 'a'];
    }
} 

Trie

Class Trie {
   TrieNode root;
   public Trie()
   {
        this.root = new TrieNode();
   }
   ..
   ..
   ..
   ..
   ..
}

Insert

public void insert(String s)
{
   TrieNode current = root;
   for(int i=0;i<s.length();i++)
   {
      if(current.triesNodes[s.charAt(i) - 'a'] == null)
      {
          current.triesNodes[s.charAt(i)-'a'] = new TrieNode();
      }
      current = current.next(s.charAt(i)-'a');
   }
   current.terminating++;
}

Delete

public void delete(String s)
{
   TrieNode current = root;
   for(char c : s.toCharArray())
   {
      if(current != null)
      current = current.next(c-'a');
   }
    if(current != null && current.terminating > 0)
    current.terminating--;
    else
    System.out.println("There is no string to delete");
}

Search

public int search(String s)
{
   TrieNode current = root;
   for(int i=0;i<s.length();i++)
   {
      if(current == null || current.next(s.charAt(i)-'a')
      return 0;
      else
      current = current.next(s.charAt(i)-'a');
   }
   return current.terminating;
}

Thanks to Gaurav Sen, for helping me to make this article.

For reference : https://github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/Tries.java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s