A Trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set of strings. Tries are used for efficient retrieval of keys in a dataset of strings, providing fast search, insert, and delete operations.
Consider a Trie that stores the words 'cat', 'car', 'cart', and 'dog':
root
/ \
c d
/ \ \
a a o
/ \ \
t r g
\ \
t
In this Trie, each node represents a character, and paths from the root to the leaves represent words in the dataset.
Tries have several important properties:
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()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")
trie.insert("dog")
print(trie.search("car")) # Output: True
print(trie.search("bat")) # Output: False
print(trie.starts_with("ca")) # Output: True
print(trie.starts_with("do")) # Output: True
This code defines a Trie with methods for inserting words, searching for exact matches, and checking for prefixes.
Tries are a powerful data structure that provides efficient management and retrieval of strings. Understanding their components, properties, and applications is crucial for implementing various algorithms and solving complex problems in fields like text processing, networking, and bioinformatics.