Standard Tries

Tries are tree-like data structures that are mainly used for storing dynamic set of strings or associative arrays where the keys are usually strings. The word "trie" comes from the word "retrieval".

We already discussed the basic concepts of tries in Tries chapter. In this chapter, we will discuss the standard tries in data structures.

What is Standard Trie?

Children of a node are stored in a certain order such as dictionary order (alphabetical) or ASCII order. The order des on the use cases. For example, if the trie is used for a dictionary, the children are stored in alphabetical order.

Let's understand with an example.

We have an array of Strings.
{cat, car, dog, doll}
The structure of the trie for these strings would be
                   (root)
             	    /\
             	   /  \
             	  /    \
                  /      \
                 c        d
                / \      / \
               a   a    o   o
              /    \   /     \
             t      r l       g
                   /
                  l

The above example shows the standard trie structure for the strings {cat, car, dog, doll}. The root node is empty and the children are stored in alphabetical order.

In the Standard Trie, a string can be traced from the root node to the node where the strings. The node is marked as a leaf node.

Operations on Standard Trie

There are mainly three operations that can be performed on a standard trie:

• Insert: Inserting a new string in the trie.
• Search: Searching a string in the trie.
• Delete: Deleting a string from the trie.

Implementation of Standard Trie

For implementing the standard trie, we need to create a structure for the trie node. The trie node contains an array of pointers to the children nodes and a flag to mark the of the string.

Now, let's implement the standard trie, which supports the above operations.

Insert Operation on Standard Trie

Inserting a new string in the Standard Trie is done by inserting the characters of the string one by one. The characters are inserted in the trie in the order of the string. The last character of the string is marked as a leaf node.

Algorithm for Insert Operation in Standard Trie

Following is the algorithm for the insert operation in the standard trie:

1.Traverse the trie from the root node.
2.Insert the characters of the string one by one.
3.Mark the last character of the string as a leaf node.

Code for Insert Operation in Standard Trie

Let's see the code for the insert operation in the standard trie using C, C++, Java, and Python programming languages.

// C Program to perform Insert Operation in Standard Trie
#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

// Structure for Trie Node
struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   int iOfWord;
};

// Function to create a new Trie Node
struct TrieNode *createNode() {
   struct TrieNode *newNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
   newNode->iOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      newNode->children[i] = NULL;
   }
   return newNode;
}

// Function to insert a string in the Trie
void insert(struct TrieNode *root, char *key) {
   struct TrieNode *temp = root;
   for (int i = 0; key[i] != '\0'; i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         temp->children[index] = createNode();
      }
      temp = temp->children[index];
   }
   temp->iOfWord = 1;
}

void display(struct TrieNode *root, char str[], int level) {
   if (root->iOfWord) {
      str[level] = '\0';
      printf("%s\n", str);
   }
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      if (root->children[i]) {
         str[level] = i + 'a';
         display(root->children[i], str, level + 1);
      }
   }
}

// Main function
int main() {
   char *keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);
   struct TrieNode *root = createNode();
   for (int i = 0; i < n; i++) {
      insert(root, keys[i]);
   }
   printf("Inserted Strings are:\n");
   char str[26];
   display(root, str, 0);
   return 0;
}

Inserted Strings are:
car
cat
dog
doll

// C++ Program to perform Insert Operation in Standard Trie
#include <iostream>
#include <string>

using namespace std;
#define ALPHABET_SIZE 26

// Structure for Trie Node
struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   int iOfWord;
};

// Function to create a new Trie Node
struct TrieNode *createNode() {
   struct TrieNode *newNode = new TrieNode();
   newNode->iOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      newNode->children[i] = NULL;
   }
   return newNode;
}

// Function to insert a string in the Standard Trie
void insert(struct TrieNode *root, string key) {
   struct TrieNode *temp = root;
   for (int i = 0; i < key.length(); i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         temp->children[index] = createNode();
      }
      temp = temp->children[index];
   }
   temp->iOfWord = 1;
}

void display(struct TrieNode *root, char str[], int level) {
   if (root->iOfWord) {
      str[level] = '\0';
      cout << str <<endl;
   }
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      if (root->children[i]) {
         str[level] = i + 'a';
         display(root->children[i], str, level + 1);
      }
   }
}

// Main function
int main() {
   string keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);
   struct TrieNode *root = createNode();
   for (int i = 0; i < n; i++) {
      insert(root, keys[i]);
   }
   cout << "Inserted Strings are:" <<endl;
   char str[26];
   display(root, str, 0);
   return 0;
}

Inserted Strings are:
car
cat
dog
doll

// Java Program to perform Insert Operation in Standard Trie

class TrieNode {
   TrieNode[] children;
   boolean iOfWord;

   TrieNode() {
      children = new TrieNode[26];
      iOfWord = false;
   }
}

public class Main {
   // Function to insert a string in the Standard Trie
   public static void insert(TrieNode root, String key) {
      TrieNode temp = root;
      for (int i = 0; i < key.length(); i++) {
         int index = key.charAt(i) - 'a';
         if (temp.children[index] == null) {
            temp.children[index] = new TrieNode();
         }
         temp = temp.children[index];
      }
      temp.iOfWord = true;
   }

   static void display(TrieNode root, char[] str, int level) {
      if (root.iOfWord) {
         str[level] = '\0';
         System.out.println(new String(str));
      }
      for (int i = 0; i < 26; i++) {
         if (root.children[i] != null) {
            str[level] = (char)(i + 'a');
            display(root.children[i], str, level + 1);
         }
      }
   }

   // Main function
   public static void main(String[] args) {
      String[] keys = {"cat", "car", "dog", "doll"};
      int n = keys.length;
      TrieNode root = new TrieNode();
      for (int i = 0; i < n; i++) {
         insert(root, keys[i]);
      }
      System.out.println("Inserted Strings are:");
      display(root, new char[26], 0);
   }
}

Inserted Strings are:
car
cat
dog
doll

# Python Program to perform Insert Operation in Standard Trie
# Structure for Trie Node
class TrieNode:
   def __init__(self):
      self.children = [None] * 26
      self.iOfWord = False

# Function to insert a string in the Standard Trie
def insert(root, key):
   temp = root
   for i in range(len(key)):
      index = ord(key[i]) - ord('a')
      if not temp.children[index]:
         temp.children[index] = TrieNode()
      temp = temp.children[index]
   temp.iOfWord = True

def display(root, str, level):
   if root.iOfWord:
      print(''.join(str[:level]))
   for i in range(26):
      if root.children[i]:
         str[level] = chr(i + ord('a'))
         display(root.children[i], str, level + 1)

# Main function
if __name__ == "__main__":
    keys = ["cat", "car", "dog", "doll"]
    n = len(keys)
    root = TrieNode()
    for i in range(n):
        insert(root, keys[i])
    print("Inserted Strings are:")
    display(root, [''] * 26, 0)

car
cat
dog
doll

Search Operation on Standard Trie

Searching a string in the Standard Trie is done by traversing the trie from the root node to the node where the strings. If the string is found in the trie, then the search operation returns true; otherwise, it returns false.

Algorithm for Search Operation in Standard Trie

Following is the algorithm for the search operation in the Standard Trie:

1.Traverse the trie from the root node.
2.Search the characters of the string one by one.
3.If the string is found, return true.
4.If the string is not found, return false.

Code for Search Operation in Standard Trie

Following is the code for the search operation in the Standard Trie using C, C++, Java, and Python programming languages.

// C Program to perform Search Operation in Standard Trie
#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

// Structure for Trie Node
struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   int iOfWord;
};

// Function to create a new Trie Node
struct TrieNode *createNode() {
   struct TrieNode *newNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
   newNode->iOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      newNode->children[i] = NULL;
   }
   return newNode;
}

// Function to insert a string in the Standard Trie
void insert(struct TrieNode *root, char *key) {
   struct TrieNode *temp = root;
   for (int i = 0; key[i] != '\0'; i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         temp->children[index] = createNode();
      }
      temp = temp->children[index];
   }
   temp->iOfWord = 1;
}

// Function to search a string in the Standard Trie
int search(struct TrieNode *root, char *key) {
   struct TrieNode *temp = root;
   for (int i = 0; key[i] != '\0'; i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         return 0;
      }
      temp = temp->children[index];
   }
   return temp != NULL && temp->iOfWord;
}

int main() {
   char *keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);
   struct TrieNode *root = createNode();
   for (int i = 0; i < n; i++) {
      insert(root, keys[i]);
   }
   search(root, "cat") ? printf("Found\n") : printf("Not Found\n");
   return 0;
}

Found

// C++ Program to perform Search Operation in Standard Trie
#include <iostream>
using namespace std;

#define ALPHABET_SIZE 26

// Structure for Trie Node
struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   int iOfWord;
};

// Function to create a new Trie Node
struct TrieNode *createNode() {
   struct TrieNode *newNode = new TrieNode();
   newNode->iOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      newNode->children[i] = NULL;
   }
   return newNode;
}

// Function to insert a string in the Standard Trie
void insert(struct TrieNode *root, string key) {
   struct TrieNode *temp = root;
   for (int i = 0; i < key.length(); i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         temp->children[index] = createNode();
      }
      temp = temp->children[index];
   }
   temp->iOfWord = 1;
}

// Function to search a string in the Standard Trie
bool search(struct TrieNode *root, string key) {
   struct TrieNode *temp = root;
   for (int i = 0; i < key.length(); i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         return false;
      }
      temp = temp->children[index];
   }
   return temp != NULL && temp->iOfWord;
}

int main() {
   string keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);
   struct TrieNode *root = createNode();
   for (int i = 0; i < n; i++) {
      insert(root, keys[i]);
   }
   search(root, "cat") ? cout << "Found" <<endl : cout << "Not Found" <<endl;
   return 0;
}

Found

// Java Program to perform Search Operation in Standard Trie
class TrieNode {
   TrieNode[] children;
   boolean iOfWord;

   TrieNode() {
      children = new TrieNode[26];
      iOfWord = false;
   }
}

public class Main {
   // Function to insert a string in the Standard Trie
   public static void insert(TrieNode root, String key) {
      TrieNode temp = root;
      for (int i = 0; i < key.length(); i++) {
         int index = key.charAt(i) - 'a';
         if (temp.children[index] == null) {
            temp.children[index] = new TrieNode();
         }
         temp = temp.children[index];
      }
      temp.iOfWord = true;
   }

   // Function to search a string in the Standard Trie
   public static boolean search(TrieNode root, String key) {
      TrieNode temp = root;
      for (int i = 0; i < key.length(); i++) {
         int index = key.charAt(i) - 'a';
         if (temp.children[index] == null) {
            return false;
         }
         temp = temp.children[index];
      }
      return temp != null && temp.iOfWord;
   }

   // Main function
   public static void main(String[] args) {
      String[] keys = {"cat", "car", "dog", "doll"};
      int n = keys.length;
      TrieNode root = new TrieNode();
      for (int i = 0; i < n; i++) {
         insert(root, keys[i]);
      }
      System.out.println(search(root, "monkey") ? "Found" : "Not Found");
   }
}

Not Found

# Python Program to perform Search Operation in Standard Trie

# Structure for Trie Node
class TrieNode:
   def __init__(self):
      self.children = [None] * 26
      self.iOfWord = False

# Function to insert a string in the Standard Trie
def insert(root, key):
   temp = root
   for i in range(len(key)):
      index = ord(key[i]) - ord('a')
      if not temp.children[index]:
         temp.children[index] = TrieNode()
      temp = temp.children[index]
   temp.iOfWord = True

# Function to search a string in the Standard Trie
def search(root, key):
   temp = root
   for i in range(len(key)):
      index = ord(key[i]) - ord('a')
      if not temp.children[index]:
         return False
      temp = temp.children[index]
   return temp != None and temp.iOfWord

# Main function
if __name__ == "__main__":
   keys = ["cat", "car", "dog", "doll"]
   n = len(keys)
   root = TrieNode()
   for i in range(n):
       insert(root, keys[i])
   print("Found" if search(root, "cat") else "Not Found")

Found

Delete Operation on Standard Trie

Deleting a string from the Standard Trie is done by deleting the characters of the string one by one. The characters are deleted in the order of the string. The last character of the string is marked as a non-leaf node.

Algorithm for Delete Operation in Standard Trie

Following is the algorithm for the delete operation in the Standard Trie:

1.Traverse the trie from the root node.
2.Delete the characters of the string one by one.
3.Mark the last character of the string as a non-leaf node.

Code for Delete Operation in Standard Trie

Let's see the code for the delete operation in the Standard Trie using C, C++, Java, and Python programming languages.

// C Program to perform Delete Operation in Standard Trie
#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   int iOfWord;
};

struct TrieNode *createNode() {
   struct TrieNode *newNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
   newNode->iOfWord = 0;
   for (int i = 0; i < ALPHABET_SIZE; i++) {
      newNode->children[i] = NULL;
   }
   return newNode;
}

void insert(struct TrieNode *root, char *key) {
   struct TrieNode *temp = root;
   for (int i = 0; key[i] != '\0'; i++) {
      int index = key[i] - 'a';
      if (!temp->children[index]) {
         temp->children[index] = createNode();
      }
      temp = temp->children[index];
   }
   temp->iOfWord = 1;
}

int delete(struct TrieNode *root, char *key, int depth) {
   if (root == NULL) {
      return 0;
   }
   
   if (key[depth] == '\0') {
      if (root->iOfWord) {
         root->iOfWord = 0;
      }
      for (int i = 0; i < ALPHABET_SIZE; i++) {
         if (root->children[i]) {
            return 0;
         }
      }
      free(root);
      return 1;
   }

   int index = key[depth] - 'a';
   if (delete(root->children[index], key, depth + 1)) {
      root->children[index] = NULL;
      if (!root->iOfWord) {
         for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (root->children[i]) {
               return 0;
            }
         }
         free(root);
         return 1;
      }
   }
   return 0;
}

void display(struct TrieNode *root, char str[], int level) {
   if (root == NULL) {
      return;
   }

   if (root->iOfWord) {
      str[level] = '\0';
      printf("%s\n", str);
   }

   for (int i = 0; i < ALPHABET_SIZE; i++) {
      if (root->children[i]) {
         str[level] = i + 'a';
         display(root->children[i], str, level + 1);
      }
   }
}

int main() {
   char *keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);
   struct TrieNode *root = createNode();

   for (int i = 0; i < n; i++) {
      insert(root, keys[i]);
   }

   printf("Before Deletion:\n");
   char str[20];
   display(root, str, 0);

   delete(root, "car", 0);

   printf("\nAfter Deletion:\n");
   display(root, str, 0);

   return 0;
}

Before Deletion:
car
cat
dog
doll

After Deletion:
cat
dog
doll

// C++ Program to perform Delete Operation in Standard Trie
#include <iostream>
#include <cstdlib>

using namespace std;

#define ALPHABET_SIZE 26

struct TrieNode {
   TrieNode *children[ALPHABET_SIZE];
   bool iOfWord;

   TrieNode() {
      iOfWord = false;
      for (int i = 0; i < ALPHABET_SIZE; i++) {
         children[i] = nullptr;
      }
   }
};

class Trie {
public:
   TrieNode *root;

   Trie() {
      root = new TrieNode();
   }

   void insert(const string &key) {
      TrieNode *temp = root;
      for (char ch : key) {
         int index = ch - 'a';
         if (!temp->children[index]) {
            temp->children[index] = new TrieNode();
         }
         temp = temp->children[index];
      }
      temp->iOfWord = true;
   }

   bool deleteKey(TrieNode *root, const string &key, int depth) {
      if (!root) {
         return false;
      }

      if (depth == key.length()) {
         if (root->iOfWord) {
            root->iOfWord = false;
         }
         for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (root->children[i]) {
               return false;
            }
         }
         delete root;
         return true;
      }

      int index = key[depth] - 'a';
      if (deleteKey(root->children[index], key, depth + 1)) {
         root->children[index] = nullptr;
         if (!root->iOfWord) {
            for (int i = 0; i < ALPHABET_SIZE; i++) {
               if (root->children[i]) {
                  return false;
               }
            }
            delete root;
            return true;
         }
      }
      return false;
   }

   void deleteKey(const string &key) {
      deleteKey(root, key, 0);
   }

   void display(TrieNode *root, string &str, int level) {
      if (root == nullptr) {
         return;
      }

      // If it's the of a word, print the string accumulated so far.
      if (root->iOfWord) {
         str[level] = '\0';
         cout << str <<endl;
      }

      // Recur for all children
      for (int i = 0; i < ALPHABET_SIZE; i++) {
         if (root->children[i]) {
            str[level] = i + 'a';  // Add current character to the string
            display(root->children[i], str, level + 1);
         }
      }
   }

   void display() {
      string str(100, '\0');  // Create a string of size 100
      display(root, str, 0);   //  the traversal
   }
};

int main() {
   Trie trie;

   string keys[] = {"cat", "car", "dog", "doll"};
   int n = sizeof(keys) / sizeof(keys[0]);

   for (int i = 0; i < n; i++) {
      trie.insert(keys[i]);
   }

   cout << "Before Deletion:" <<endl;
   trie.display();

   trie.deleteKey("car");

   cout << "\nAfter Deletion:" <<endl;
   trie.display();

   return 0;
}

Before Deletion:
car
cat
dog
doll

After Deletion:
cat
dog
doll

// Java Program to perform Delete Operation in Standard Trie

class TrieNode {
   TrieNode[] children;
   boolean iOfWord;

   TrieNode() {
      children = new TrieNode[26];
      iOfWord = false;
   }
}

public class Main {
   // Function to insert a string in the Standard Trie
   public static void insert(TrieNode root, String key) {
      TrieNode temp = root;
      for (int i = 0; i < key.length(); i++) {
         int index = key.charAt(i) - 'a';
         if (temp.children[index] == null) {
            temp.children[index] = new TrieNode();
         }
         temp = temp.children[index];
      }
      temp.iOfWord = true;
   }

   // Function to delete a string from the Standard Trie
   public static boolean delete(TrieNode root, String key, int depth) {
      if (root == null) {
         return false;
      }

      if (depth == key.length()) {
         if (root.iOfWord) {
            root.iOfWord = false;
         }
         for (int i = 0; i < 26; i++) {
            if (root.children[i] != null) {
               return false;
            }
         }
         return true;
      }

      int index = key.charAt(depth) - 'a';
      if (delete(root.children[index], key, depth + 1)) {
         root.children[index] = null;
         if (!root.iOfWord) {
            for (int i = 0; i < 26; i++) {
               if (root.children[i] != null) {
                  return false;
               }
            }
            return true;
         }
      }
      return false;
   }

   // Main function
   public static void main(String[] args) {
      String[] keys = {"cat", "car", "dog", "doll"};
      int n = keys.length;
      TrieNode root = new TrieNode();
      for (int i = 0; i < n; i++) {
         insert(root, keys[i]);
      }

      System.out.println("Before Deletion:");
      display(root, "", 0);

      delete(root, "car", 0);

      System.out.println("\nAfter Deletion:");
      display(root, "", 0);
   }

   // Function to display the Standard Trie
   public static void display(TrieNode root, String str, int level) {
      if (root == null) {
         return;
      }

      if (root.iOfWord) {
         System.out.println(str);
      }

      for (int i = 0; i < 26; i++) {
         if (root.children[i] != null) {
            display(root.children[i], str + (char)(i + 'a'), level + 1);
         }
      }

   }
}

Before Deletion:
car
cat
dog
doll

After Deletion:
cat
dog
doll

# Python Program to perform Delete Operation in Standard Trie

# Structure for Trie Node
class TrieNode:
   def __init__(self):
      self.children = [None] * 26
      self.iOfWord = False

class Trie:
   def __init__(self):
      self.root = TrieNode()

   def insert(self, key):
      temp = self.root
      for i in range(len(key)):
         index = ord(key[i]) - ord('a')
         if not temp.children[index]:
            temp.children[index] = TrieNode()
         temp = temp.children[index]
      temp.iOfWord = True

   def delete(self, root, key, depth):
      if not root:
         return False

      if depth == len(key):
         if root.iOfWord:
            root.iOfWord = False
         for i in range(26):
            if root.children[i]:
               return False
         return True

      index = ord(key[depth]) - ord('a')
      if self.delete(root.children[index], key, depth + 1):
         root.children[index] = None
         if not root.iOfWord:
            for i in range(26):
               if root.children[i]:
                  return False
            return True
      return False

   def display(self, root, str, level):
      if not root:
         return

      if root.iOfWord:
         print(str)

      for i in range(26):
         if root.children[i]:
            self.display(root.children[i], str + chr(i + ord('a')), level + 1)

if __name__ == "__main__":
   trie = Trie()
   
   keys = ["cat", "car", "dog", "doll"]
   n = len(keys)
   
   for i in range(n):
      trie.insert(keys[i])
   
   print("Before Deletion:")
   trie.display(trie.root, "", 0)
   
   trie.delete(trie.root, "car", 0)
   
   print("\nAfter Deletion:")
   trie.display(trie.root, "", 0)

Before Deletion:
car
cat
dog
doll

After Deletion:
cat
dog
doll

Time Complexity of Standard Trie

Following is the time complexity of the Standard Trie:

• Insert Operation: O(n), where n is the length of the string.
• Search Operation: O(n).
• Delete Operation: O(n).

Applications of Standard Trie

Standard Trie is used in various applications such as:

• Spell Checker
• Auto-Complete
• Dictionary
• IP Routing
• Network Routing
• Prefix Matching

These are some of the applications where Standard Trie is used.

Conclusion

In this chapter, we discussed the Standard Trie in data structures. The structure of the Standard Trie, the operations that can be performed on the Standard Trie, and the implementation of the Standard Trie. We also discussed the applications of the Standard Trie.