Trie
A trie or prefix tree is used for associating words in a given alphabet
to some values in .
- This is given by a directed rooted tree
. - An edge letter map
, where . - A node key map
where is a null value. Then every word
in has a path in where and . Then either or has no edge labelled . We then can use this to associate a value to it is the last non-null value in the sequence or it is null.