ref

Prefix tree

1. Building a well balanced BST needs time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
2. Using trie, search in O(M) time.
3. The penalty is on trie storage requirements.

Implementation

1. Every node of trie consists of multiple branches.
2. Each branch represents a possible character of keys.

3. Mark the last node of every key as leaf node.

   struct trie_node { int value; / Used to mark leaf nodes / trie_node_t *children[ALPHABET_SIZE]; };

Note that a non-terminating node can also be marked as leaf. Eg.

                   root
                /   \    \
                t  'a'    b
                |   |     |
                h   n    'y'
                |   |  \    \
               'e'  s  'y'  'e'
             /  |   |
            i   r   w
           /    |   |
         'r'   'e'  e
                    |
                   'r'

The leaf nodes are quoted in ‘’.

Insert and search costs O(key_length), however the memory requirements of trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in trie.

Compressed trie, ternary search tree, etc. can be used to minimize memory requirements of trie.