Tag Archives: trie

Trie

Trie or prefix tree is a tree-like data structure that implements dictionary abstract data type. In other words, trie allows to store key/value pairs in hierarchical structure. For example, let say we have words {a, as, air, aim, ail, car, i, milk, be, bag}. These words can be represented as follows.

trie_intro4

As you can see the root of the trie is an empty string that has five direct children. Every child represents first letter of a given word so that the words with the same prefix share the common nodes. As a result, a key can consist of one or more nodes, but values stored in one node.

Continue reading Trie