The Trie

Let A be a finite Alphabeth. A trie is a rooted tree with the following properties:
  1. The edges of the tree are marked with letters out of A (so-called labels).
  2. For each node k of the tree and for each letter c of A. there is at most one edge which starts in k and is marked with c
Given a node k of the trie, path(k) denotes the string built by the labels on the way from the root to k.

Let P be a set of strings, then trie(P) is the smallest (with respect to the number of nodes) trie with the following property:

For all pat of P exists a node k< such that pat = path(k)

Example: P = {ab, ba, babb, bb}


Trie.