Trie (thing)

In data structure terminology, a trie is a 26-ary tree useful for the storage and retrieval of alphabetic strings. Each node in the trie contains a list of 26 node pointers, corresponding to letters of the alphabet, as well as any data field(s) pertinent to the strings being stored.

To add a string to the trie, one starts at the root node, and follows the node pointers corresponding to each letter of the string in turn, adding new nodes as needed. When the string has been consumed, the current node will represent this particular string, so any data the programmer wishes to associate with it should be placed in this node. Or, if the trie is just meant to store strings (for instance, if it holds a word processor's spell checking dictionary), the data of the last node should merely indicate the end of a string. Thus, it can be seen that most nodes are merely stepping-stones to the end of a string or strings.

Similarly, to locate the data associated with a string (or to see if the trie contains the string at all), start at the root and follow the branch dictated by each character of the string in turn. The data of the last node arrived at (if any) is what you're looking for.

Here's an example implementation of a generic trie in C:

typedef struct trie_node {
	void *data;
	struct trie_node *branch[26];
} trie_node;

trie_node *new_trie_node( void )
{
	trie_node *new;
	int i;
	new = (trie_node*)malloc(sizeof(trie_node));
	new->data = NULL;
	for ( i = 0; i < 26; i++ )
		new->branch[i] = NULL;
}

void trie_add( trie_node *node, char *s, void *data )
/* add string s to the trie and attach data to it */
{
	if ( !*s ) node->data = data;
	else {
		int idx = *s - 'a';
		if ( !node->branch[idx] )
			node->branch[idx] = new_trie_node();
		trie_add(node->branch[idx], s+1, data);
	}
}

void *trie_get( trie_node *node, char *s )
/* return data associated with string s, or NULL if not found */
{
	if ( !node ) return NULL;
	if ( !*s ) return node->data;
	return trie_get(node->branch[*s - 'a'], s+1);
}

Note in trie_get that although the second base case might be reached and satisfied, this does not necessarily mean "success," because the string being sought could be exhausted before we reach a node with any data. This would indicate a partial match; in other words, the string being sought was a prefix of one or more strings contained in the trie, but not an actual entry. One neat side-effect of the trie's structure is that it lends itself to string completion (getting a list of possible matches for a given prefix.)

Initially, one might be tempted to think that each node should keep a record of what character it represents, but this is unnecessary; the structure of the trie itself dictates what each node represents. Or, put differently, how you got to this node defines the string so far. Any path from the root node to a node with non-empty data delimits a string.

Complexity of the add and get operations is O(n), where n is the length of the string in question.