Some results on V-ary asymmetric tries

Tries (radix search tries) find many applications in computer science and telecommunications. It is assumed that a trie is built over an alphabet U = {σ₁,…,σ_v} (V-ary trie), and n (possible infinite) strings of elements from U (i.e., keys) are stored in external nodes of the trie. The occurrence of an element σ_i in a key is represented by a probability p_i (asymmetric trie). Our main interest is to compute all moments of the depth of a leaf (external node) in a random family of tries. By solving a system of recurrences we find an exact formula for all factorial moments of the depth, and—using the Mellin transform technique—we derive asymptotic approximations for them. We prove that the m th factorial moment of the depth of a leaf in a trie with n keys is equal to αln^mn + βln^m−1n + O(ln^m−2n), where the constants α and β are functions of the probabilities, p_i, i = 1,…,V. In particular, we show that for symmetric tries the variance of the depth is O(1), while for asymmetric tries it is αlnn + O(1), and we determine explicitly the constant O(1). These results extend previous analyses by Knuth 12], Flajolet and Sedgewick 6], Jacquet and Regnier 10], and Kirschenhofer and Prodinger 11].