concept trie in category algorithms
This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14.
If you feel that figure 6.2 is a bit confusing… you are right, it is: in their classic implementation, trie’s nodes have one edge for each possible character in the alphabet used: some of these edges point to other nodes, most of them (especially in the lower levels of the tree) are null references[9].
Figure 6.2 The structure of a Trie. Words are encoded in the tree one using edges, each edge corresponds to a single character, and each node n is associated with a single word, the one obtained by joining the characters associated with the edges in the path from the root to n: the root node corresponds to the empty string (because no edge is traversed), the leftmost leaf corresponds to “aa”, etc… Not all the paths make meaningful words, and indeed not all the nodes store the word associated with them: only filled, black nodes (called “key nodes”) mark words stored in the trie, while hollow nodes, aka “intermediate nodes”, corresponds to prefixes of words stored in the trie. Notice that all leaves should be key nodes.
Formally, given an alphabet ∑ with |∑|=k symbols, a trie is a k-ary[10] tree where each node has (at most) k children, each one marked with a different character in ∑; links can point to another node, or to null.
Figure 6.3 A more compact representation of a trie. This example trie contains the same elements as the binary search tree in figure 6.1.
Unlike k-ary search trees, though, no node in the tree actually stores the key associated with it. Instead, the characters held in the trie are actually stored in the edges between a node and its children.
Listing 6.1 illustrates a possible implementation of a Trie class (in an object-oriented pseudocode); you can also take a look at a full implementation on the book’s repo on GitHub. In the simplest version, trie’s nodes can only hold a tiny piece of information, just true or false: when marked with true, a node N is called a “key node”, because it means that the sequence of characters in the edges of the path from the root to N corresponds to a word that is actually stored in the trie.
Nodes holding false, instead, are called “intermediate nodes”, because they correspond to intermediate characters of one or more words stored in the trie.