✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-201

Trie 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

Words

  • CAR

  • CAT

  • CARE

  • DOG

Shared Prefix

CA

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.

Key Concepts

  • Tree-based string storage

  • Prefix sharing

  • Character edges

  • Terminal nodes

  • Prefix searching

  • Node insertion and deletion

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