An Analysis of the Height of Tries with Random Weights on the Edges

Source abstract

We analyse the weighted height of random tries built from independent strings of i.i.d. symbols on the finite alphabet {1, . . . d }. The edges receive random weights whose distribution depends upon the number of strings that visit that edge. Such a model covers the hybrid tries of de la Briandais and the TST of Bentley and Sedgewick, where the search time for a string can be decomposed as a sum of processing times for each symbol in the string. Our weighted trie model also permits one to study maximal path imbalance. In all cases, the weighted height is shown to be asymptotic to c log n in probability, where c is determined by the behaviour of the core of the trie (the part where all nodes have a full set of children) and the fringe of the trie (the part of the trie where nodes have only one child and form spaghetti -like trees). It can be found by maximizing a function that is related to the Cramér exponent of the distribution of the edge weights.