Trie

Introduction

A Trie is a data structure for storing a set of strings.

It is represented as a tree where the edges are labeled with characters.

Each node corresponds to the string formed by reading all characters on the path from the root to that node.

The root represents the empty string.

Building the Tree

Initially, the Trie consists of a single node: the root.

Let edge(x, g) denote the node reached from node x by following the edge labeled with character g.

Adding a String

Suppose we want to add a string $S$ of length $m$.

We start at the root:

• let x = root

Then for each character S[i]:

• if the edge edge(x, S[i]) already exists, we follow it;
• otherwise, we create a new node, add the corresponding edge, and then follow it.

At the end, the final node represents the whole string $S$. We mark this node as terminal.

Searching for a String

To find a string $S$, we start from the root and follow the edges corresponding to its characters one by one.