Related Tags

tries
data structures
communitycreator

# What are tries and their types?

Buchiredddypalli Koushik

### Trie

Trie is a tree-like data structure where data is stored in the treeâ€™s nodes. Nodes can have one, more than one, or no children.

Tries are generally used in string search applications like auto-search, IP routing.

We classify them into the three following types:

• Standard trie
• Compressed trie
• Suffix tree

In this shot, weâ€™ll discuss the standard and compressed trie.

### Standard trie

A Standard trie is an ordered tree in which each node is labeled with a character except for the root node.

If we want to generate a string, we traverse through the treeâ€™s nodes.

### Example

String S = {ball, box, bomb, basket, stock, stop}

In standard trie, every traversal from the root node represents one of the words in the string S.

Standard trie

### Compressed trie

A compressed trie is a compact representation of a standard trie.

If we have a node with one child, we try to merge them to get the easy form of the trie.

### Example

Compressed trie

Representation of a compressed tree:

     0 1 2 3 4 5


S[0] = b a l l

S[1] = b o x

S[2] = b o m b

S[3] = b a s k e t

S[4] = s t o c k

S[5] = s t o p

We represent a compressed trie in three tuple notation:

Node(i, j, k)

• i represents index of S at which the word is present.

• j represents the index at which the prefix starts.

• k represents the index at which the prefix ends.

Compressed trie

RELATED TAGS

tries
data structures
communitycreator

CONTRIBUTOR

Buchiredddypalli Koushik
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time