Trie in Python using OOP concepts

In this article, we have implemented Trie Data Structure in Python Programming Language using OOP concepts. We have explained the implementation design step by step.

Basic Idea on Trie

Before stepping into implemetation part, we will see what actually is a trie .Trie is a tree like datastructure which is used to store a collection of strings and it is also known as prefix tree or a digital tree.

The trie consists of nodes that are connected by edges.There will be a root node of the trie which represents an empty string and the children of each node will represent next character in the word.

Example:{cap,car,dog}

         (root)
          /  \
         c    d
        / \    \
       a   a    o
      /     \    \
     p      r    g

From this example, we can infer that root has two children "c" and "d" .The node "c" has two children "a" and "p" ,which represents prefix "ca" and the word is "cap" .Similarly,the node "d" has two children "o" and "g" ,which represent the prefix "do" and the word is "dog" .The node "a" has two children "p" and "r" ,which represent the prefix "car" and the word is "car".

Implementation

• Define the Trienode class:This class represents a single node in the Trie.It contains a dictionary to store the children of node's and boolean flag to indicate if it is end of word.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

• Define the Trie class:It contains the root node which is single instance variable.

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

• The insert method: This is the first step in implementation of trie that is inserting a new word into the trie.It should iterate over each character in the word and adds a new node to the trie it doesn't exist before.Finally,the node in the word should be marked as the end of a word.
• The search method:This is second step in implementation of trie that is searching for a word in a trie.If the word is present then it returns true and if word is not present it returns false.
• The starts_with method:This method checks if any word in a trie will start with the prefix which is given .It will iterate down each character in the prefix and traverse down the trie until the prefix is reacher or the character is not found .If the prefix end is reached the method will return true,if not ir returns false.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False


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

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_of_word = True

    def search(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.end_of_word

    def starts_with(self, prefix: str) -> bool:
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

Example

For a proper picture of the given code we will look into an example:

trie = Trie()

# Insert some words into the Trie
trie.insert("apple")
trie.insert("banana")
trie.insert("orange")
trie.insert("pear")

# Search for some words in the Trie
print(trie.search("apple"))  # Output: True
print(trie.search("banana"))  # Output: True
print(trie.search("grape"))  # Output: False

# Check if any words start with a prefix
print(trie.starts_with("app"))  # Output: True
print(trie.starts_with("ban"))  # Output: True
print(trie.starts_with("gra"))  # Output: False

In this example,we first created an instance of the Trie class .
We inserted words into the Trie using the 'insert' method. We are inserting 'apple','banana','orange' and 'pear' into the trie.

Next we search for some words if they are present in the trie or not using the 'search' method .Here we are searching for 'apple','banana' and 'grape'.As 'apple' is present in the trie it will return true as output next it will search for banana if as 'banana' is present in the trie the output which it returns will be true .'grape' is not present in the given trie so it returns false as output.

Finally,we will check for the words in the Trie with a prefix using 'starts_with' method.We check if any of the words in the Trie starts with the prefixes 'app','ban' and 'gra' .The first two will return true as output as the word 'apple' and 'banana' will start with the give prefix but for the third one it will return false because it is not prefix for any of the word given in the Trie.

Applications of Trie

1. AutoComplete:Tries are used in autocomplete features in text editors.As the user types something in the search bar the trie will suggest the possible matches for the prefix which user types
2. Spell checking:If there is a wrong spelling trie will suggest the correct spelling for the words which are misspelled.It also finds the similar words to the word which is misspelled by searching for words with a similar prefix.
3. Dictionary:Tries are used in dictionaries to store and retrive words.Every word in the dictionary is stored as a node in the trie,and the travarsel of the trie can be used to search words.
4. Pattern Matching:Tries are effective for pattern matching as they allow for efficient search of a set of patterns in a text string. The patterns are stored in the trie as nodes, and a search for a pattern involves traversing the trie until a match is found.

Overall, tries are a versitile data structure that is useful in a variety of applications.