Types of Tries in Python
Introduction to Trie
A Trie or different Types of Tries used for retrieval tree or digital tree, is a tree-like data structure used for efficiently storing and searching a dynamic set of keys, usually strings. Trie is also known as Digital Tree or Prefix Tree.
There are mainly three types of trie : Standard trie, Compressed trie and Suffix trie.
What is Trie ? Describe its types.
A trie is a tree-shaped data structure that stores information in its nodes, and these nodes can possess either one, more than one, or no children.
It is also known as Digital Tree or Radical Tree or Prefix Tree.
Types of Tries in Data Structure
There are mainly three types of tries in data structure :
- Standard Trie
- Compressed Trie
- Suffix Trie
1. Standard Trie
In a standard trie, each node represents a single character in a key or string. The root node is associated with the empty string, and each edge corresponds to a character in the string.
Characteristics of Standard Trie:
- Nodes may have multiple children, each associated with a different character.
- The key is usually stored at the leaf node, and the path from the root to the leaf represents the key.
- Efficient for exact match searches and insertion of keys.
- Can be memory-intensive, especially for datasets with a large number of keys.
Code Example:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
# Example
trie = Trie()
trie.insert("cat")
print(trie.search("cat")) # True
print(trie.search("car")) # False
Output:
True False
Explanation:
- TrieNode holds a dictionary of children and a flag for word ending.
- insert() iterates through each character, creating new nodes if needed.
- search() traverses through nodes, checking if each character exists.
- The is_end flag ensures the exact word is matched, not just a prefix.
- cat returns True because it exists, car returns False because it was not inserted.
Time & Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert | O(m) | O(m * n) |
| Search | O(m) | O(1) |
2. Compressed Trie
Compressed tries use various techniques to reduce memory usage. One common approach is path compression, where chains of single-child nodes are condensed into a single node.
Characteristics of Compressed Trie:
- Compact representation achieved by eliminating redundant single-child nodes.
- Reduces memory requirements compared to standard tries.
- Search and insertion operations may be slightly more complex due to the need for decompression during traversal.
- Suitable for scenarios where memory efficiency is crucial.
Code Example:
class CompressedTrie:
def __init__(self):
self.trie = {}
def insert(self, word):
node = self.trie
while True:
for key in list(node.keys()):
prefix_len = 0
while prefix_len < min(len(word), len(key)) and word[prefix_len] == key[prefix_len]: prefix_len += 1 if prefix_len > 0:
if prefix_len < len(key):
node[word[:prefix_len]] = {key[prefix_len:]: node.pop(key)}
node = node[word[:prefix_len]]
word = word[prefix_len:]
break
else:
node[word] = {}
return
def display(self, node=None, prefix=''):
if node is None:
node = self.trie
for key, child in node.items():
print(prefix + key)
self.display(child, prefix + key)
# Example
ct = CompressedTrie()
ct.insert("cat")
ct.insert("car")
ct.insert("dog")
ct.display()
Output:
cat car dog
Explanation:
- Compressed Trie merges consecutive single-child paths into one key.
- insert() checks for common prefixes to avoid storing extra nodes.
- New words are split only when a mismatch occurs in the prefix.
- display() prints stored words efficiently.
- The structure is memory-optimized compared to a standard trie.
Time & Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert | O(m) | O(k) |
| Search | O(m) | O(1) |
3. Suffix Trie
Suffix tries are specialized structures designed for handling dynamic sets of strings and pattern matching. They store all the suffixes of a given string.
Characteristics of Suffix Trie:
- Efficient for substring searches and pattern matching.
- Each leaf node represents a suffix of the original string.
- Useful in applications such as text indexing, bioinformatics (DNA sequence analysis), and data compression algorithms.
- Construction of a suffix trie is typically more involved and may require additional algorithms, such as Ukkonen’s algorithm.
class SuffixTrie:
def __init__(self, text):
self.root = {}
self.end_symbol = "*"
self.build(text)
def build(self, text):
for i in range(len(text)):
node = self.root
for j in range(i, len(text)):
ch = text[j]
if ch not in node:
node[ch] = {}
node = node[ch]
node[self.end_symbol] = True
def search(self, pattern):
node = self.root
for ch in pattern:
if ch not in node:
return False
node = node[ch]
return self.end_symbol in node
# Example
st = SuffixTrie("banana")
print(st.search("ana"))
print(st.search("nana"))
print(st.search("apple"))
True True FalseExplanation:
- Suffix Trie stores all suffixes of the input string.
- The build() method inserts every suffix starting at each index.
- The * symbol marks the end of a suffix.
- search() traverses character by character to match the pattern.
- Fast for substring searches but uses more memory.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Build | O(n²) | O(n²) |
| Search (pattern) | O(m) | O(1) |
Components of Trie
Nodes and Edges:
- A trie is composed of nodes, each representing a single character in a key or string.
- Edges connect the nodes and correspond to characters, forming paths from the root to the leaf nodes.
Root Node:
- The topmost node, known as the root, has no associated character but serves as the starting point for traversing the trie.
Leaf Nodes:
- Leaf nodes represent the end of a key or string and often store additional information associated with that key.
Applications of Tries
Following are the applications of Tries in Data Structure :
To Wrap it up:
The trie data structure is a powerful tool for organizing and retrieving data efficiently, especially in scenarios where quick searches and pattern matching are critical. In summary, a standard trie provides a straightforward representation of keys, but it can be memory-intensive. Compressed tries optimize memory usage by eliminating redundant nodes. Suffix tries, on the other hand, are specialized for substring searches and pattern matching, storing all suffixes of a string.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
FAQs
The main types are Standard Trie, Compressed Trie (Radix Tree), and Suffix Trie. Each serves different storage and search optimizations.
A Standard Trie stores strings character by character, making prefix-based searching efficient in O(m) time, where m is the length of the word.
A Compressed Trie merges single-child paths into one edge, reducing space usage and improving lookup speed for sparse datasets.
A Suffix Trie stores all suffixes of a string, allowing fast substring search, pattern matching, and text analysis in linear time.
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
Login/Signup to comment