Overview
A suffix tree compresses chains of suffix trie edges, enabling many substring and pattern queries in linear or near-linear time.
CoreSource checked
Suffix Tree
Stores all suffixes of a string in a compressed trie for fast substring queries.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Advanced
- Family
- String Index
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 8
- Code example
- Ready
- Visualization
- Ready
Core Concepts
compressed triesuffix linkedge labelsubstring query
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(m)
Average
O(m)
Worst
O(m)
Space
O(n)
When to Use
- Use when fast lookup needs compressed trie.
- Use when the input matches the assumptions behind string Index.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Stores all suffixes of a string in a compressed trie for fast substring queries
- Uses compressed trie and suffix link to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Pseudocode
- 1.Initialize the storage layout and invariants
- 2.For each update, locate the affected position or node
- 3.Modify pointers, counters, buckets, or summary values
- 4.Repair invariants such as balance, order, or load bounds
- 5.Answer queries from the maintained structure
Canonical Example
- Input
- Suffix Tree
- Output
- Stored structure
- Explanation
- Suffix Tree applies compressed trie to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the compressed trie step separate enough to test independently.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Test edge cases, not only clean examples.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 5: Initialize the storage layout and invariants
data-structures-mechanismNotes
Suffix Tree should be used with the assumptions and tradeoffs of string Index in mind.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Suffix Tree's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Suffix Tree's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesRope
Data Structures · Core
Ropes optimize editable text storage, while suffix trees index substrings for search.
Compare with thisAlternative toSuffix Array
Data Structures · Core
Suffix trees and suffix arrays are different full-text index structures.
Compare with thisAlternativesSuffix Automaton LCS
Pattern Matching · Core
Suffix trees provide another indexed structure for longest common substring queries.
Compare with thisAlternativesSuffix Array Search
Pattern Matching · Extended
Suffix arrays and suffix trees support substring queries with different space tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toSuffix Array
Suffix trees and suffix arrays are different full-text index structures.
Conceptual neighborSuffix Automaton
Both compactly represent substring structure.
Related Algorithms
Tags
Data StructureStringsSuffix IndexPrefix Tree