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:

 1class TrieNode:
 2    def __init__(self):
 3        self.children = {}
 4        self.is_end_of_word = False
 5
 6class Trie:
 7    def __init__(self):
 8        self.root = TrieNode()
 9
10    def insert(self, word):
11        node = self.root
12        for char in word:
13            if char not in node.children:
14                node.children[char] = TrieNode()
15            node = node.children[char]
16        node.is_end_of_word = True
17
18    def search(self, word):
19        node = self.root
20        for char in word:
21            if char not in node.children:
22                return False
23            node = node.children[char]
24        return node.is_end_of_word
25
26    def starts_with(self, prefix):
27        node = self.root
28        for char in prefix:
29            if char not in node.children:
30                return False
31            node = node.children[char]
32        return True
33
34# Example usage
35trie = Trie()
36words = ["apple", "app", "apricot", "bear", "bet"]
37for word in words:
38    trie.insert(word)
39
40print(trie.search("apple"))    # True
41print(trie.search("app"))      # True
42print(trie.search("appl"))     # False
43print(trie.starts_with("app")) # True
44print(trie.starts_with("bea")) # True
45print(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!