Trie in Python

October 17, 2023

Introduction to Trie in Python

Trie in Python, also known as prefix trees, are a fascinating data structure used in computer science for efficient string matching and retrieval operations.

In this article, we will delve into the world of Trie in Python, exploring their structure, applications, and how to implement them

What is trie?

Trie are tree-like data structures that are particularly useful for solving problems related to strings and text.
The name “Trie” comes from the word “retrieval” because these structures excel at retrieving data associated with a specific key or prefix.
Tries are prominently used in various applications, such as autocomplete systems, spell checkers, and IP routing tables.

Basic Trie Structure

A Trie consists of nodes, where each node represents a character in a word or string. These nodes are connected in a hierarchical manner, forming a tree-like structure.
The root node represents an empty string, and as you traverse down the Trie, you build words character by character.

Trie Operations

Insertion You can add a new word or string to the Trie by inserting its characters one by one, starting from the root node and creating new nodes as needed.

Deletion Deleting a word from a Trie can be slightly more complex than insertion and search but is still manageable.

Search Searching for a specific word in a Trie is efficient, as it involves traversing the Trie's nodes character by character. If you reach the end of a word while traversing, it means the word exists in the Trie.

Implementation Of Trie in Python

let’s see how we can implement a Trie in Python. We will create a basic Trie structure and demonstrate insertion and search operations.

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

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

Advantages of Trie in Python

Tries in Python offer several advantages:

Efficient Retrieval: Tries excel in searching for words or strings efficiently, making them ideal for autocomplete and spell-check applications.

Space Efficiency: Tries are memory-efficient for storing large sets of words with shared prefixes.

Prefix Matching: Tries can quickly find all words with a common prefix, enabling advanced text searching.

Analysis of the Algorithm

Python trie library

To get started, you’ll need to install the pytrie library if you haven’t already. You can install it using pip:

pip install pytrie

Once you have pytrie installed, you can use it to create and manipulate trie data structures. Here’s a basic example of how to use it:

from pytrie import StringTrie

# Create a trie
trie = StringTrie()

# Insert keys into the trie
trie["apple"] = 1
trie["app"] = 2
trie["banana"] = 3
trie["bat"] = 4

# Check if a key exists in the trie
print("Is 'apple' in trie?", "apple" in trie)  # True
print("Is 'apricot' in trie?", "apricot" in trie)  # False

# Retrieve values associated with keys
print("Value of 'apple':", trie.get("apple"))  # 1
print("Value of 'app':", trie.get("app"))  # 2

# Find keys with a common prefix
print("Keys with prefix 'ap':", list(trie.keys(prefix="ap")))  # ['app', 'apple']
print("Keys with prefix 'ba':", list(trie.keys(prefix="ba")))  # ['banana', 'bat']

# Delete a key from the trie
del trie["apple"]
print("Is 'apple' in trie after deletion?", "apple" in trie)  # False

In this example, we create a StringTrie, insert keys with associated values, and perform various operations like checking for key existence, retrieving values, and finding keys with common prefixes.
The pytrie library is a convenient tool for working with trie data structures in Python, making it easier to implement tasks like autocompletion, searching for words with common prefixes, and more.

Python trie dictionary

A Python Trie Dictionary, often referred to as a TrieMap or TrieDict, is a data structure that combines the characteristics of a trie and a dictionary (or hashmap).
It allows you to efficiently store key-value pairs, where the keys are strings, and provides fast retrieval and insertion of these pairs.

Here’s an example of how to implement a simple Trie Dictionary in Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.value = None

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

    def insert(self, key, value):
        node = self.root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.value = value

    def search(self, key):
        node = self.root
        for char in key:
            if char not in node.children:
                return None
            node = node.children[char]
        return node.value

    def starts_with_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def delete(self, key):
        def _delete(node, key, depth):
            if depth == len(key):
                if node.value is not None:
                    node.value = None
                    return len(node.children) == 0
                return False

            char = key[depth]
            if char not in node.children:
                return False

            should_delete_child = _delete(node.children[char], key, depth + 1)
            if should_delete_child:
                del node.children[char]
                return len(node.children) == 0

            return False

        _delete(self.root, key, 0)

# Example usage:
trie_dict = TrieDictionary()
trie_dict.insert("apple", 42)
trie_dict.insert("banana", 17)

print("Search 'apple':", trie_dict.search("apple"))  # Output: 42
print("Search 'banana':", trie_dict.search("banana"))  # Output: 17
print("Search 'cherry':", trie_dict.search("cherry"))  # Output: None

print("Starts with prefix 'app':", trie_dict.starts_with_prefix("app"))  # Output: True

trie_dict.delete("apple")
print("Search 'apple' after deletion:", trie_dict.search("apple"))  # Output: None

Aspect	Trie	HashTable
Data Retrieval Speed	O(K) for lookup, where K is key length	O(1) average-case lookup (with possible collisions)
Memory Usage	Can be memory-intensive, especially with common prefixes	Generally memory-efficient, except with many collisions
Prefix-Based Operations	Ideal for prefix-based operations like autocomplete	Not designed for prefix-based operations
Key Types	Primarily for string keys	Can handle various key types (integers, strings, custom objects)

Use Cases of Tries in Python

Autocomplete and Suggestions: Tries are commonly used in search engines, text editors, and applications that require autocomplete or suggestions. As a user types a query, a trie can quickly retrieve a list of matching words or phrases, making the user experience more interactive and responsive.
Spell Checkers: Tries can be employed to implement spell-checking algorithms. Each node in the trie represents a valid prefix or word, and the spell checker can traverse the trie to suggest corrections for misspelled words.
Dictionary and Lexicon: Tries are an excellent choice for implementing dictionaries and lexicons. They can efficiently store and retrieve words, making them useful for word games, language processing, and language translation applications.
IP Routing: In networking, tries can be used for IP address routing and packet forwarding. IP routing tables can be implemented using a trie data structure to efficiently determine the next-hop destination for a given IP address.

Conclusion

Trie in Python are a versatile and powerful data structure for handling string-related operations efficiently. Whether you’re building a spell checker, an autocomplete system, or dealing with text data in any way, Tries can be your go-to solution. Understanding the structure and applications of Tries is a valuable skill for any programmer.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others