Day 58: Tries

Table of Contents

Day 58: Tries #

Welcome to Day 58 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Tries, an efficient tree-like data structure used for storing and retrieving strings.

What is a Trie? #

A Trie, also called a prefix tree, is a tree-like data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

Properties of Tries #

  1. The root represents an empty string.
  2. Each node (except the root) stores a character and has up to 26 children (for English alphabet).
  3. Each path from the root to a node represents a prefix of one or more strings.
  4. Nodes can store additional information, like whether they represent the end of a word.

Implementation #

Here’s a Python implementation of a Trie:

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

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

# Example usage
trie = Trie()
words = ["apple", "app", "apricot", "bear", "bet"]
for word in words:
    trie.insert(word)

print(trie.search("apple"))    # True
print(trie.search("app"))      # True
print(trie.search("appl"))     # False
print(trie.starts_with("app")) # True
print(trie.starts_with("bea")) # True
print(trie.starts_with("bec")) # False

Time Complexity #

  • Insertion: O(m), where m is the length of the word
  • Search: O(m), where m is the length of the word
  • Prefix Search: O(p), where p is the length of the prefix

Space Complexity #

The space complexity is O(n * m), where n is the number of words and m is the average length of the words.

Advantages of Tries #

  1. Efficient prefix-based operations
  2. Faster than hash tables for certain operations
  3. Can provide an alphabetical ordering of entries by key

Disadvantages of Tries #

  1. Can be slower than hash tables for simple key lookups
  2. Requires more space than other data structures for small sets of strings

Applications of Tries #

  1. Autocomplete and spell checkers
  2. IP routing tables in network routers
  3. Implementing dictionaries
  4. Search engines for prefix matching

Variations and Optimizations #

  1. Compressed Trie (Radix Tree): Merges nodes with only one child
  2. Ternary Search Tree: A type of trie where nodes have three children
  3. Suffix Tree: A compressed trie of all suffixes of a given string

Exercise #

  1. Implement a function to delete a word from the Trie.
  2. Modify the Trie to store the frequency of each word.
  3. Implement an autocomplete function that returns all words in the Trie with a given prefix.

Summary #

Today, we explored Tries, an efficient tree-like data structure for storing and retrieving strings. We implemented a basic Trie, discussed its time and space complexity, and looked at its advantages, disadvantages, and applications.

Tries are particularly useful in scenarios involving prefix matching and string retrieval, making them valuable in various applications like autocomplete systems, spell checkers, and IP routing.

Tomorrow, we’ll dive into Advanced Tree Structures, building upon the tree concepts we’ve learned so far. Stay tuned!