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.

%0 node_1 Root node_2 b node_1->node_2 node_3 s node_1->node_3 node_1642220918749 a node_2->node_1642220918749 node_1642221011041 o node_2->node_1642221011041 node_1642220930748 l node_1642220918749->node_1642220930748 node_1642221039232 s node_1642220918749->node_1642221039232 node_1642220933901 l node_1642220930748->node_1642220933901 node_1642221059631 k node_1642221039232->node_1642221059631 node_1642221067324 e node_1642221059631->node_1642221067324 node_1642221065473 t node_1642221067324->node_1642221065473 node_1642220989680 x node_1642221011041->node_1642220989680 node_1642220998419 m node_1642221011041->node_1642220998419 node_1642220977871 b node_1642220998419->node_1642220977871 node_1642221180985 t node_3->node_1642221180985 node_1642221220408 o node_1642221180985->node_1642221220408 node_1642221212395 c node_1642221220408->node_1642221212395 node_1642221250173 o node_1642221220408->node_1642221250173 node_1642221180631 k node_1642221212395->node_1642221180631
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

%0 node_1 Root node_2 b node_1->node_2 node_3 sto node_1->node_3 node_1642221617575 a node_2->node_1642221617575 node_1642221821678 o node_2->node_1642221821678 node_1642221767989 ll node_1642221617575->node_1642221767989 node_1642221718316 sket node_1642221617575->node_1642221718316 node_1642221828040 x node_1642221821678->node_1642221828040 node_1642221857444 mb node_1642221821678->node_1642221857444 node_1642221723699 ck node_3->node_1642221723699 node_1642221700904 p node_3->node_1642221700904
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.

%0 node_1 Root node_2 0,0,0 node_1->node_2 node_3 4,0,2 node_1->node_3 node_1642222671837 0,1,1 node_2->node_1642222671837 node_1642222874741 1,1,1 node_2->node_1642222874741 node_1642222762041 0,2,3 node_1642222671837->node_1642222762041 node_1642222977793 3,2,5 node_1642222671837->node_1642222977793 node_1642222884762 1,2,2 node_1642222874741->node_1642222884762 node_1642222921153 2,2,3 node_1642222874741->node_1642222921153 node_1642222680160 4,3,4 node_3->node_1642222680160 node_1642222647379 5,3,3 node_3->node_1642222647379
Compressed trie

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)