Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Computing Atlas

Two Trees Built From Position, Not Content

Back to Interesting Facts

In a trie, first described in 1959, the meaning of a stored string lives in the node's position in the tree, not in anything written inside the node itself. Each edge stands for exactly one character, so any two strings that share a prefix walk the identical path down from the root for as long as that shared prefix lasts, and only diverge onto separate edges at the first character where they differ. That single design choice is what lets a trie answer an autocomplete suggestion or a dictionary lookup by walking one character at a time from the root, rather than comparing whole candidate strings against each other one by one. The suffix tree, introduced fourteen years later in 1973, is not a separate idea built to solve a separate problem. Its own attested description names it directly: a compressed trie holding every suffix of a string at once. Where an ordinary trie stores a collection of separate strings, a suffix tree takes a single string and tries every one of its own suffixes into the same structure, then compresses the runs of one-child paths so the whole thing stays proportional in size to the original string rather than to the much larger set of suffixes it represents. The payoff of building that structure is specific and measurable: a query for whether some other string appears anywhere inside it can be answered in a number of steps proportional only to the length of the string being searched for, not the length of the string being searched in, which is exactly the property that makes it useful for fast string search, genome analysis and data compression.

Where To Read More