Today we start Section 5.2, on tries.

We would like symbol tables for strings (that is, where the keys are
strings) taking advantage of some of the same ideas that we saw for
string sorting.  That is, instead of treating the key as an atomic
thing, we treat it as a sequence of chars in some alphabet.

We would like speed (like we expect in hashing) but also allowing
operations on string order and on prefixes.

We'll look at several "trie" structures (pronounced "try").
Basically, a "trie" is a sort of tree for storing strings, where the
sequence of symbols in the key correspond to a path to find the key in
the tree.  There are several variations on this basic idea, depending
on issues like your alphabet size (R), and available memory.

The naive Trie is not memory efficient (at least for large R).  One
alternative would be to use a tiny R (e.g. R=2).  Another alternative
is the "TST": essentially we do a binary search on each char of the
key.  (There are also some other alternative trie designs, but beyond
our textbook apparently.)

Note that for each single char search, the TST is a naive BST.  It
could benefit from the same rebalancing tricks we have already know
for BST's (AVL, red-black, random insertion order, or rebuild).  With
such balancing, we can guarantee worst case O(L + lg N) nodes visited
per search for a key of length L.

See:
   52Tries.pdf (through page 32 for Trie and TST)
   52DemoTrie.mov
   52DemoTST.mov

Furthermore, if there is time, we will see that tries (either
the naive Trie, or the TST) support some new operations: e.g.
ordered traversal, and some two variations of "prefix search".

Finally we might see "trie compression", which is essential in
order to represent a "suffix tree" in linear space.  (It turns
out that the "suffix tree" can also be computed in linear time,
but that is quite difficult to describe.)