Tries

Overview

The word trie comes from the word retrieval. A trie is also known as a digital tree, radix tree or prefix tree.

Each node contains the following:

1. A value, which can be null.
2. An array of pointers to child nodes, where each one may optionally be null.

A trie usually has an empty root node (or ""). This root node contains a list of nodes, one for each character in the alphabet (e.g. 26 entries for English). The characters are mapped to pointers in the array by their index, where A = 0 and Z = 25.

The value is used to indicate whether or not the sequence of letters from the root node to the current node form a valid word (if they don’t, they only exist because there is a larger word which contains these letters).

Tries are one way to implement an associative array.

Complexity

The worst case time to construct a trie is dependent on the product of the longest word $m$, and how many words the trie contains $n$. This is written using Big-O notation as $\mathcal{O}(mn)$. The time it takes for insertion, deletion and searching is dependent only on the length of the word you are inserting, deleting or searching for $a$ — it is independent of the total number of words in the trie. This is expressed as $\mathcal{O}(a)$.

Uses

Tries are used in the following ways:

• Search engines
• Spell-checkers
• Auto-complete