Tries

A trie is a tree data structure often used to store strings. Every leaf of the trie represents one string. Each node on the path from root to leaf is labeled with exactly one character of the string. Information on this page is taken from section 12.3 of The Algorithm Design Manual by Steven S. Skiena.

Here's a trie on strings the, their, there, was, and when.

Tries are useful for testing whether a given query string q is in the set. We traverse the trie from the root along branches defined by successive characters of q. If a branch does not exist in the trie, then q cannot be in the set of strings. Otherwise we find q in |q| character comparisons regardless of how many strings are in the trie.

A suffix tree is a trie of all proper suffixes of \(S\). A suffix tree enables one to test whether \(q\) is a substring of \(S\), because any substring of \(S\) is a prefix of some suffix. Here's a suffix tree on elliot.

Constructed naively, a suffix tree requires \(O(n^2)\) time and space. A compressed trie, however, requires linear space. This trie is obtained by joining chains of single nodes. The nodes of a compressed trie also often store index ranges instead of actual strings. Here's a compressed suffix tree on elliot.