What are tries and their types?

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.

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

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.