Analysis of hybrid tries

Digital trees or tries are a general purpose flexible data structure implementing dictionaries built on a set of strings over some fixed alphabet. The aim is to analyze some classical parameters of tries (namely the number of internal nodes and the external path length) for various implementations, including the ``ternary search trie'' of Bentley and Sedgewick. Indeed, although keeping the overall trie structure, several options are possible depending on the way descendants of a node are represented in the tree structure. The three major choices which present themselves are arrays of pointers, ordered lists and binary search trees. The methods employed combine symbolic uses of generating functions, Poisson models and Mellin transforms. Theoretical results are matched against real-life data and justify the claim that ternary search tries are a highly efficient dynamic dictionary structure for strings.