ALGORITHMS AND DATA STRUCTURES

# 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, 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