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:

“What I want to say, Linda,

is that there is nothing in your body that lies.

All that is new is telling the truth.

I’m here, that somebody else,

an old *tree* in the background.”

—Anne Sexton (1928–1974)