Trie Structure Introduction
A Trie Tree (also known as a prefix tree or radix tree) is a tree data structure used for efficiently storing and retrieving sets of strings. Its primary characteristic is the utilization of common prefixes to effectively compress storage space and accelerate string lookup operations.
The core idea of a Trie Tree involves splitting each string into a series of character nodes, where the relationship between characters is represented by links between nodes. Below are the main characteristics and basic operations of a Trie Tree:
Structural Characteristics: A Trie Tree is a multi-way tree where each node represents a character, and the path from the root node to a leaf node represents a complete string. The root node does not store a character; every non-root node stores one character and may have zero or more child nodes.
Insertion Operation: To insert a string into a Trie Tree, start from the root node and traverse each character of the string in sequence. If the child node corresponding to the current character does not exist, create a new node; if the child node corresponding to the current character already exists, move directly to the next character. Repeat this process until the last character of the string is reached. The node corresponding to the last character is marked as a terminating node, indicating that the string has been successfully inserted into the Trie Tree.
Query Operation: To query a string, start from the root node and traverse each character of the target string in sequence. If the child node corresponding to the current character exists, move to the next character; if the child node corresponding to the current character does not exist, it indicates that the string is not present in the Trie Tree, resulting in a failed query. Repeat this process until the last character of the string is reached. If the node corresponding to the last character is a terminating node, it means the string exists in the Trie Tree, and the query is successful; otherwise, the query fails.
Prefix Matching: A Trie Tree can efficiently perform prefix matching operations. Start from the root node and traverse each character of the prefix string to be matched in sequence. If the child node corresponding to the current character exists, move to the next character; if the child node corresponding to the current character does not exist, it indicates that the prefix string is not present in the Trie Tree, resulting in a failed match. Repeat this process until the last character of the prefix string is reached. There is no need to determine whether the node corresponding to the last character is a terminating node; as long as every character of the prefix string exists in the Trie Tree, it can be determined that the match is successful.
The advantage of a Trie Tree lies in its efficient insertion and query operations, with a time complexity of O(L), where L is the length of the string. It is suitable for scenarios requiring the efficient storage and retrieval of large sets of strings, such as word lookup, auto-completion, spell checking, and string search.
However, the disadvantage of a Trie Tree is its relatively high memory consumption, particularly when storing a large number of long strings, which can lead to significant space overhead. Additionally, if there are many duplicate prefixes in the set of strings, using a compressed Trie (or compacted trie) can reduce the usage of storage space.
Code Example: Basic Insert and Search
class TrieNode:
"""Represents a node in the Trie Tree."""
def __init__(self):
# Initialize children dictionary and termination flag
self.children = {} # Maps character to TrieNode
self.is_terminating = False # Flag to mark if this string ends here
class TrieTree:
"""A simple implementation of a Trie Tree."""
def __init__(self):
# The root node does not store a character itself
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the Trie Tree.
Args:
word (str): The string to be inserted.
"""
current_node = self.root
for char in word:
# Check if the child node for the current character exists
if char not in current_node.children:
# If not, create a new node
current_node.children[char] = TrieNode()
# Move to the next character's node
current_node = current_node.children[char]
# Mark the last node as a terminating node
current_node.is_terminating = True
def search(self, word: str) -> bool:
"""
Searches for a word in the Trie Tree.
Args:
word (str): The string to search for.
Returns:
bool: True if the word exists, False otherwise.
"""
current_node = self.root
for char in word:
# If the child node for the current character does not exist,
# the word is not in the Trie Tree
if char not in current_node.children:
return False
# Move to the next character's node
current_node = current_node.children[char]
# The word exists only if the last node is a terminating node
return current_node.is_terminating
def starts_with(self, prefix: str) -> bool:
"""
Checks if any word in the Trie Tree starts with the given prefix.
Args:
prefix (str): The prefix string to check.
Returns:
bool: True if a word with this prefix exists, False otherwise.
"""
current_node = self.root
for char in prefix:
# If the child node for the current character does not exist,
# the prefix is not found
if char not in current_node.children:
return False
# Move to the next character's node
current_node = current_node.children[char]
# No need to check is_terminating for prefix matching
return True
# Example Usage
if __name__ == "__main__":
trie = TrieTree()
# Insert some words
trie.insert("apple")
trie.insert("app")
trie.insert("application")
# Search operations
print(trie.search("apple")) # Output: True
print(trie.search("apply")) # Output: False
print(trie.search("app")) # Output: True
# Prefix matching operations
print(trie.starts_with("appl")) # Output: True
print(trie.starts_with("apricot")) # Output: False