concept · INFO-CS-ADS-201Trie Data Structure
Understand how a Trie stores strings character by character in a tree structure to support efficient prefix searching and word retrieval.
Explanation
Overview
A Trie, also called a prefix tree, is a tree-based data structure used to store and retrieve strings. Each edge represents a character, and a path from the root represents a sequence of characters. A special terminal marker indicates that a complete word ends at a particular node.
Key concepts
Tree-based string storage; Prefix sharing; Character edges; Terminal nodes; Prefix searching; Node insertion and deletion
Complexity
insertion: O(L) expected time with suitable child lookup.; search: O(L) expected time with suitable child lookup.; prefixSearch: O(P) to reach the prefix node, plus the cost of enumerating matching words.; space: O(total stored characters) in a basic implementation, with significant overhead possible from node and child structures.; variables: L is the length of the word and P is the length of the prefix.
Example
words: CAR; CAT; sharedPrefix: CA; explanation: CAR, CAT, and CARE share the prefix CA, so their paths reuse the same initial nodes. DOG follows a separate branch.
Pseudocode
function insert(root, word):
current = root
for character in word:
if character not in current.children:
current.children[character] = new TrieNode()
current = current.children[character]
current.isEndOfWord = true
function search(root, word):
current = root
for character in word:
if character not in current.children:
return false
current = current.children[character]
return current.isEndOfWord
Applications
Autocomplete systems.; Dictionary applications.; Spell checking.; IP routing tables.; Search suggestions.; Prefix-based filtering.
Advantages
Search time depends primarily on the length of the queried word rather than the number of stored words.; Supports efficient prefix queries.; Shares common prefixes between stored strings.; Can provide autocomplete suggestions.; Avoids comparing every stored word from the beginning.
Example or application
Explanation
CAR, CAT, and CARE share the prefix CA, so their paths reuse the same initial nodes. DOG follows a separate branch.
Definition
A Trie, also called a prefix tree, is a tree-based data structure used to store and retrieve strings. Each edge represents a character, and a path from the root represents a sequence of characters. A special terminal marker indicates that a complete word ends at a particular node.
Fundamental Structure
Root
The starting node representing an empty prefix.
Edge
A connection labeled with a character.
Child
A node reached by following a character edge.
Terminal Marker
Indicates that the path from the root forms a complete stored word.
Prefix
A sequence of characters shared by one or more stored words.
Common Operations
Insert
Adds a word by following or creating the necessary character edges and marking the final node as terminal.
Search
Follows the characters of a word and checks whether the final node is marked as terminal.
Starts With
Checks whether a path corresponding to a given prefix exists.
Delete
Removes the terminal marker and deletes unnecessary nodes that are no longer part of another stored word.
Prefix Search
Locates all words beginning with a specified prefix.
Pseudocode
function insert(root, word):
current = root
for character in word:
if character not in current.children:
current.children[character] = new TrieNode()
current = current.children[character]
current.isEndOfWord = true
function search(root, word):
current = root
for character in word:
if character not in current.children:
return false
current = current.children[character]
return current.isEndOfWord
Complexity
Insertion
O(L) expected time with suitable child lookup.
Search
O(L) expected time with suitable child lookup.
Prefix Search
O(P) to reach the prefix node, plus the cost of enumerating matching words.
Space
O(total stored characters) in a basic implementation, with significant overhead possible from node and child structures.
Variables
L is the length of the word and P is the length of the prefix.
Advantages
Search time depends primarily on the length of the queried word rather than the number of stored words.
Supports efficient prefix queries.
Shares common prefixes between stored strings.
Can provide autocomplete suggestions.
Avoids comparing every stored word from the beginning.
Limitations
Can consume substantial memory when many nodes have few children.
Node and pointer overhead may be larger than storing strings in a simple array.
Child lookup performance depends on the chosen representation.
Large character alphabets may require more flexible child structures.
Applications
Autocomplete systems.
Dictionary applications.
Spell checking.
IP routing tables.
Search suggestions.
Prefix-based filtering.
Related Topics
Prefix Trees
Suffix Trees
Hash Tables
String Searching
Tree Data Structures
Practice Question
Why can a Trie search for a word efficiently without comparing it against every stored word?
Practice Answer
It follows the word's characters through a shared tree path, taking time mainly proportional to the word's length.
Learning Objectives
Explain the central idea and purpose of trie data structure.
Identify the assumptions, inputs, and conditions relevant to trie data structure.
Evaluate an application of trie data structure for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- String Algorithms and Pattern Matching
Suggest a correction or source · More in Algorithms & Data Structures