Trie in Python

Trie In Python

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 Data Structure

Trie Operations

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:

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
AspectTrieHashTable
Data Retrieval SpeedO(K) for lookup, where K is key lengthO(1) average-case lookup (with possible collisions)
Memory UsageCan be memory-intensive, especially with common prefixesGenerally memory-efficient, except with many collisions
Prefix-Based OperationsIdeal for prefix-based operations like autocompleteNot designed for prefix-based operations
Key TypesPrimarily for string keysCan handle various key types (integers, strings, custom objects)

Use Cases of Tries in Python

  1. 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.
  2. 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.
  3. 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.
  4. 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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription