A Uniform Approach to the Analysis of Trie Structures That Store Prefixing-Keys

Triesare data structures for storing sets where each element is represented by a key that can be viewed as a string of characters over a finite alphabet. These structures have been extensively studied and analyzed under several probability models. All of these models, however, preclude the occurrence of sets in which the key of one element is a prefix of that of another—such a key is called aprefixing-key. This paper presents an average case analysis of several trie varieties, which we generically calledprefixing-tries, for representing sets with “unrestricted” keys, that is, sets in which the key of one element may be a prefix of that of another. The underlying probability model, which we call theprefix model, _{h, n, m}assumes as equally likely alln-element sets whose keys are composed of at mosthcharacters from a fixed alphabet of sizem. For each of the trie varieties analyzed, we derive exact formulas for the expected space required to store such a set, and the average time required to retrieve an element given its key, as functions ofh,n, andm. Our approach to the analysis is of interest in its own right. It provides a unifying framework for computing the expectations of a wide class of random variables with respect to the prefix model. This class includes the cost functions of the trie varieties analyzed here.