Suffix Tree is mainly used to search a pattern in a text.

The idea is to preprocess the text so that search operation can be done in time linear in terms of pattern length. The pattern searching algorithms like KMP, Z, etc take time proportional to text length. Suffix Tree is compressed trie/ radix tree of all suffixes, so following are very abstract steps to build a suffix tree from given text.

1. Generate all suffixes of given text.
2. Consider all suffixes as individual words and build a compressed trie.

#### Example:

• Find occurrences of pattern
• Search a pattern in a text

Suffix Tree may not be a good idea when text changes frequently like a text editor, etc.

### Data Structure

#### Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

#### Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

#### B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

#### Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

#### Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

#### AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

#### KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)