Tries

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, were 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).

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 on the product of the length of the word you are inserting, deleting or searching for \( a \), and the total number of words \( n \). This is expressed as \( \mathcal{O}(an) \).

Uses

Tries are used in the following ways:

• Search engines
• Spell-checkers
• Auto-complete