There are two ways to reduce the memory consumption of a trie- reduce the number of nodes (as the techniques mentioned above attempt to do), or reduce the amount of memory required by each node. In this section, we will explore a technique that attempts to do the latter.
The problem is that the array of pointers to children is typically very sparse. We have seen sparse arrays before, so we know an approach to this problem: instead of storing the array explicitly as an ordinary C array, we can store the array as a linked list. This technique is generally called a de la Briandais tree (after Rene de la Briandais, who developed many of the ideas behind the practical implementation and application of tries). An example of a de la Briandais tree is shown in figure 5.7.
Figure 5.7:
A de la Briandais tree containing ``hi'' and ``ho''.
Traversing a linked list to find a child pointer (or discover that there is not one) is a considerably more expensive operation than a simple array lookup, so tries implemented in this manner are not as time-efficient as our array-based tries. The decrease in speed is proportional, in the worst case, to the size of the character set in use- for our example application, where there are 26 possible characters, we might need to examine as many as 25 linked list elements at each node before we find the child we are looking for, or determine that it does not exist. However, this slowdown is proportional in the worst case to the size of the alphabet, and is not related in any way to the number of keys in the trie or their lengths.
Nodes that have many children may actually require more memory to represent using linked lists than arrays, since the linked list cells themselves require more memory than the array elements, but if the trie is sparse then the savings can be dramatic.