In computer science, a **suffix tree** (also called **PAT tree** or, in an earlier form, **position tree**) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.

The suffix tree for a string is a tree whose edges are labeled with strings, such that each suffix of corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree (more specifically, a Patricia tree) for the suffixes of .

Constructing such a tree for the string takes time and space linear in the length of . Once constructed, several operations can be performed quickly, for instance locating a substring in, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provided one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.

Read more about Suffix Tree: History, Definition, Generalized Suffix Tree, Functionality, Applications, Implementation, External Construction

### Famous quotes containing the word tree:

“The Anglo-American can indeed cut down, and grub up all this waving forest, and make a stump speech, and vote for Buchanan on its ruins, but he cannot converse with the spirit of the *tree* he fells, he cannot read the poetry and mythology which retire as he advances. He ignorantly erases mythological tablets in order to print his handbills and town-meeting warrants on them.”

—Henry David Thoreau (1817–1862)