New results on the size of tries
Mireille Régnier, Philippe Jacquet · IEEE Transactions on Information Theory · 1989
A precise asymptotic expansion of the variance of the size of a trie built on random binary strings is presented. This data structure appears in some hashing schemes and communications protocols. The variance is asymptotically linear, and numerical results are given. The reader is referred to an earlier work for formal proofs.>